1 /**CFile****************************************************************
2
3 FileName [abcUtil.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Network and node package.]
8
9 Synopsis [Various utilities.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: abcUtil.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "abc.h"
22 #include "base/main/main.h"
23 #include "map/mio/mio.h"
24 #include "bool/dec/dec.h"
25 #include "opt/fxu/fxu.h"
26 #include "aig/miniaig/ndr.h"
27
28 #ifdef ABC_USE_CUDD
29 #include "bdd/extrab/extraBdd.h"
30 #endif
31
32 ABC_NAMESPACE_IMPL_START
33
34
35 ////////////////////////////////////////////////////////////////////////
36 /// DECLARATIONS ///
37 ////////////////////////////////////////////////////////////////////////
38
39 ////////////////////////////////////////////////////////////////////////
40 /// FUNCTION DEFINITIONS ///
41 ////////////////////////////////////////////////////////////////////////
42
43 /**Function*************************************************************
44
45 Synopsis [Frees one attribute manager.]
46
47 Description []
48
49 SideEffects []
50
51 SeeAlso []
52
53 ***********************************************************************/
Abc_NtkAttrFree(Abc_Ntk_t * pNtk,int Attr,int fFreeMan)54 void * Abc_NtkAttrFree( Abc_Ntk_t * pNtk, int Attr, int fFreeMan )
55 {
56 void * pUserMan;
57 Vec_Att_t * pAttrMan;
58 pAttrMan = (Vec_Att_t *)Vec_PtrEntry( pNtk->vAttrs, Attr );
59 Vec_PtrWriteEntry( pNtk->vAttrs, Attr, NULL );
60 pUserMan = Vec_AttFree( pAttrMan, fFreeMan );
61 return pUserMan;
62 }
63
64 /**Function*************************************************************
65
66 Synopsis [Order CI/COs.]
67
68 Description []
69
70 SideEffects []
71
72 SeeAlso []
73
74 ***********************************************************************/
Abc_NtkOrderCisCos(Abc_Ntk_t * pNtk)75 void Abc_NtkOrderCisCos( Abc_Ntk_t * pNtk )
76 {
77 Abc_Obj_t * pObj, * pTerm;
78 int i, k;
79 Vec_PtrClear( pNtk->vCis );
80 Vec_PtrClear( pNtk->vCos );
81 Abc_NtkForEachPi( pNtk, pObj, i )
82 Vec_PtrPush( pNtk->vCis, pObj );
83 Abc_NtkForEachPo( pNtk, pObj, i )
84 Vec_PtrPush( pNtk->vCos, pObj );
85 Abc_NtkForEachBox( pNtk, pObj, i )
86 {
87 if ( Abc_ObjIsLatch(pObj) )
88 continue;
89 Abc_ObjForEachFanin( pObj, pTerm, k )
90 Vec_PtrPush( pNtk->vCos, pTerm );
91 Abc_ObjForEachFanout( pObj, pTerm, k )
92 Vec_PtrPush( pNtk->vCis, pTerm );
93 }
94 Abc_NtkForEachBox( pNtk, pObj, i )
95 {
96 if ( !Abc_ObjIsLatch(pObj) )
97 continue;
98 Abc_ObjForEachFanin( pObj, pTerm, k )
99 Vec_PtrPush( pNtk->vCos, pTerm );
100 Abc_ObjForEachFanout( pObj, pTerm, k )
101 Vec_PtrPush( pNtk->vCis, pTerm );
102 }
103 }
104
105 /**Function*************************************************************
106
107 Synopsis [Reads the number of cubes of the node.]
108
109 Description []
110
111 SideEffects []
112
113 SeeAlso []
114
115 ***********************************************************************/
Abc_NtkGetCubeNum(Abc_Ntk_t * pNtk)116 int Abc_NtkGetCubeNum( Abc_Ntk_t * pNtk )
117 {
118 Abc_Obj_t * pNode;
119 int i, nCubes = 0;
120 assert( Abc_NtkHasSop(pNtk) );
121 Abc_NtkForEachNode( pNtk, pNode, i )
122 {
123 if ( Abc_NodeIsConst(pNode) )
124 continue;
125 assert( pNode->pData );
126 nCubes += Abc_SopGetCubeNum( (char *)pNode->pData );
127 }
128 return nCubes;
129 }
130
131 /**Function*************************************************************
132
133 Synopsis [Reads the number of cubes of the node.]
134
135 Description []
136
137 SideEffects []
138
139 SeeAlso []
140
141 ***********************************************************************/
Abc_NtkGetCubePairNum(Abc_Ntk_t * pNtk)142 int Abc_NtkGetCubePairNum( Abc_Ntk_t * pNtk )
143 {
144 Abc_Obj_t * pNode;
145 int i;
146 word nCubes, nCubePairs = 0;
147 assert( Abc_NtkHasSop(pNtk) );
148 Abc_NtkForEachNode( pNtk, pNode, i )
149 {
150 if ( Abc_NodeIsConst(pNode) )
151 continue;
152 assert( pNode->pData );
153 nCubes = (word)Abc_SopGetCubeNum( (char *)pNode->pData );
154 if ( nCubes > 1 )
155 nCubePairs += nCubes * (nCubes - 1) / 2;
156 }
157 return (int)(nCubePairs > (1<<30) ? (1<<30) : nCubePairs);
158 }
159
160 /**Function*************************************************************
161
162 Synopsis [Reads the number of literals in the SOPs of the nodes.]
163
164 Description []
165
166 SideEffects []
167
168 SeeAlso []
169
170 ***********************************************************************/
Abc_NtkGetLitNum(Abc_Ntk_t * pNtk)171 int Abc_NtkGetLitNum( Abc_Ntk_t * pNtk )
172 {
173 Abc_Obj_t * pNode;
174 int i, nLits = 0;
175 assert( Abc_NtkHasSop(pNtk) );
176 Abc_NtkForEachNode( pNtk, pNode, i )
177 {
178 assert( pNode->pData );
179 nLits += Abc_SopGetLitNum( (char *)pNode->pData );
180 }
181 return nLits;
182 }
183
184 /**Function*************************************************************
185
186 Synopsis [Counts the number of literals in the factored forms.]
187
188 Description []
189
190 SideEffects []
191
192 SeeAlso []
193
194 ***********************************************************************/
Abc_NtkGetLitFactNum(Abc_Ntk_t * pNtk)195 int Abc_NtkGetLitFactNum( Abc_Ntk_t * pNtk )
196 {
197 Dec_Graph_t * pFactor;
198 Abc_Obj_t * pNode;
199 int nNodes, i;
200 assert( Abc_NtkHasSop(pNtk) );
201 nNodes = 0;
202 Abc_NtkForEachNode( pNtk, pNode, i )
203 {
204 if ( Abc_NodeIsConst(pNode) )
205 continue;
206 pFactor = Dec_Factor( (char *)pNode->pData );
207 nNodes += 1 + Dec_GraphNodeNum(pFactor);
208 Dec_GraphFree( pFactor );
209 }
210 return nNodes;
211 }
212
213 /**Function*************************************************************
214
215 Synopsis [Counts the number of nodes with more than 1 reference.]
216
217 Description []
218
219 SideEffects []
220
221 SeeAlso []
222
223 ***********************************************************************/
Abc_NtkGetMultiRefNum(Abc_Ntk_t * pNtk)224 int Abc_NtkGetMultiRefNum( Abc_Ntk_t * pNtk )
225 {
226 Abc_Obj_t * pNode;
227 int nNodes, i;
228 assert( Abc_NtkIsStrash(pNtk) );
229 nNodes = 0;
230 Abc_NtkForEachNode( pNtk, pNode, i )
231 nNodes += (int)(Abc_ObjFanoutNum(pNode) > 1);
232 return nNodes;
233 }
234
235 /**Function*************************************************************
236
237 Synopsis [Reads the number of BDD nodes.]
238
239 Description []
240
241 SideEffects []
242
243 SeeAlso []
244
245 ***********************************************************************/
Abc_NtkGetBddNodeNum(Abc_Ntk_t * pNtk)246 int Abc_NtkGetBddNodeNum( Abc_Ntk_t * pNtk )
247 {
248 int nNodes = 0;
249 #ifdef ABC_USE_CUDD
250 Abc_Obj_t * pNode;
251 int i;
252 assert( Abc_NtkIsBddLogic(pNtk) );
253 Abc_NtkForEachNode( pNtk, pNode, i )
254 {
255 assert( pNode->pData );
256 if ( Abc_ObjFaninNum(pNode) < 2 )
257 continue;
258 nNodes += pNode->pData? -1 + Cudd_DagSize( (DdNode *)pNode->pData ) : 0;
259 }
260 #endif
261 return nNodes;
262 }
263
264 /**Function*************************************************************
265
266 Synopsis [Reads the number of BDD nodes.]
267
268 Description []
269
270 SideEffects []
271
272 SeeAlso []
273
274 ***********************************************************************/
Abc_NtkGetAigNodeNum(Abc_Ntk_t * pNtk)275 int Abc_NtkGetAigNodeNum( Abc_Ntk_t * pNtk )
276 {
277 Abc_Obj_t * pNode;
278 int i, nNodes = 0;
279 assert( Abc_NtkIsAigLogic(pNtk) );
280 Abc_NtkForEachNode( pNtk, pNode, i )
281 {
282 assert( pNode->pData );
283 if ( Abc_ObjFaninNum(pNode) < 2 )
284 continue;
285 //printf( "%d ", Hop_DagSize( pNode->pData ) );
286 nNodes += pNode->pData? Hop_DagSize( (Hop_Obj_t *)pNode->pData ) : 0;
287 }
288 return nNodes;
289 }
290
291 /**Function*************************************************************
292
293 Synopsis [Reads the number of BDD nodes.]
294
295 Description []
296
297 SideEffects []
298
299 SeeAlso []
300
301 ***********************************************************************/
Abc_NtkGetClauseNum(Abc_Ntk_t * pNtk)302 int Abc_NtkGetClauseNum( Abc_Ntk_t * pNtk )
303 {
304 int nClauses = 0;
305 #ifdef ABC_USE_CUDD
306 extern int Abc_CountZddCubes( DdManager * dd, DdNode * zCover );
307 Abc_Obj_t * pNode;
308 DdNode * bCover, * zCover, * bFunc;
309 DdManager * dd = (DdManager *)pNtk->pManFunc;
310 int i;
311 assert( Abc_NtkIsBddLogic(pNtk) );
312 Abc_NtkForEachNode( pNtk, pNode, i )
313 {
314 assert( pNode->pData );
315 bFunc = (DdNode *)pNode->pData;
316
317 bCover = Cudd_zddIsop( dd, bFunc, bFunc, &zCover );
318 Cudd_Ref( bCover );
319 Cudd_Ref( zCover );
320 nClauses += Abc_CountZddCubes( dd, zCover );
321 Cudd_RecursiveDeref( dd, bCover );
322 Cudd_RecursiveDerefZdd( dd, zCover );
323
324 bCover = Cudd_zddIsop( dd, Cudd_Not(bFunc), Cudd_Not(bFunc), &zCover );
325 Cudd_Ref( bCover );
326 Cudd_Ref( zCover );
327 nClauses += Abc_CountZddCubes( dd, zCover );
328 Cudd_RecursiveDeref( dd, bCover );
329 Cudd_RecursiveDerefZdd( dd, zCover );
330 }
331 #endif
332 return nClauses;
333 }
334
335 /**Function*************************************************************
336
337 Synopsis [Computes the area of the mapped circuit.]
338
339 Description []
340
341 SideEffects []
342
343 SeeAlso []
344
345 ***********************************************************************/
Abc_NtkGetMappedArea(Abc_Ntk_t * pNtk)346 double Abc_NtkGetMappedArea( Abc_Ntk_t * pNtk )
347 {
348 Abc_Obj_t * pObj;
349 double TotalArea;
350 int i;
351 assert( Abc_NtkHasMapping(pNtk) );
352 TotalArea = 0.0;
353 Abc_NtkForEachNode( pNtk, pObj, i )
354 {
355 if ( Abc_ObjIsBarBuf(pObj) )
356 continue;
357 // assert( pObj->pData );
358 if ( pObj->pData == NULL )
359 {
360 printf( "Node without mapping is encountered.\n" );
361 continue;
362 }
363 TotalArea += Mio_GateReadArea( (Mio_Gate_t *)pObj->pData );
364 // assuming that twin gates follow each other
365 if ( Abc_NtkFetchTwinNode(pObj) )
366 i++;
367 }
368 return TotalArea;
369 }
370
371 /**Function*************************************************************
372
373 Synopsis [Counts the number of exors.]
374
375 Description []
376
377 SideEffects []
378
379 SeeAlso []
380
381 ***********************************************************************/
Abc_NtkGetExorNum(Abc_Ntk_t * pNtk)382 int Abc_NtkGetExorNum( Abc_Ntk_t * pNtk )
383 {
384 Abc_Obj_t * pNode;
385 int i, Counter = 0;
386 Abc_NtkForEachNode( pNtk, pNode, i )
387 Counter += pNode->fExor;
388 return Counter;
389 }
390
391 /**Function*************************************************************
392
393 Synopsis [Counts the number of exors.]
394
395 Description []
396
397 SideEffects []
398
399 SeeAlso []
400
401 ***********************************************************************/
Abc_NtkGetMuxNum(Abc_Ntk_t * pNtk)402 int Abc_NtkGetMuxNum( Abc_Ntk_t * pNtk )
403 {
404 Abc_Obj_t * pNode;
405 int i, Counter = 0;
406 Abc_NtkForEachNode( pNtk, pNode, i )
407 Counter += Abc_NodeIsMuxType(pNode);
408 return Counter;
409 }
410
411 /**Function*************************************************************
412
413 Synopsis [Counts the number of exors.]
414
415 Description []
416
417 SideEffects []
418
419 SeeAlso []
420
421 ***********************************************************************/
Abc_NtkGetBufNum(Abc_Ntk_t * pNtk)422 int Abc_NtkGetBufNum( Abc_Ntk_t * pNtk )
423 {
424 Abc_Obj_t * pNode;
425 int i, Counter = 0;
426 Abc_NtkForEachNode( pNtk, pNode, i )
427 Counter += (Abc_ObjFaninNum(pNode) == 1);
428 return Counter;
429 }
430
431 /**Function*************************************************************
432
433 Synopsis [Counts the number of exors.]
434
435 Description []
436
437 SideEffects []
438
439 SeeAlso []
440
441 ***********************************************************************/
Abc_NtkGetLargeNodeNum(Abc_Ntk_t * pNtk)442 int Abc_NtkGetLargeNodeNum( Abc_Ntk_t * pNtk )
443 {
444 Abc_Obj_t * pNode;
445 int i, Counter = 0;
446 Abc_NtkForEachNode( pNtk, pNode, i )
447 Counter += (Abc_ObjFaninNum(pNode) > 1);
448 return Counter;
449 }
450
451 /**Function*************************************************************
452
453 Synopsis [Returns 1 if it is an AIG with choice nodes.]
454
455 Description []
456
457 SideEffects []
458
459 SeeAlso []
460
461 ***********************************************************************/
Abc_NtkGetChoiceNum(Abc_Ntk_t * pNtk)462 int Abc_NtkGetChoiceNum( Abc_Ntk_t * pNtk )
463 {
464 Abc_Obj_t * pNode;
465 int i, Counter;
466 if ( !Abc_NtkIsStrash(pNtk) )
467 return 0;
468 Counter = 0;
469 Abc_NtkForEachNode( pNtk, pNode, i )
470 Counter += Abc_AigNodeIsChoice( pNode );
471 return Counter;
472 }
473
474 /**Function*************************************************************
475
476 Synopsis [Reads the maximum number of fanins.]
477
478 Description []
479
480 SideEffects []
481
482 SeeAlso []
483
484 ***********************************************************************/
Abc_NtkGetFaninMax(Abc_Ntk_t * pNtk)485 int Abc_NtkGetFaninMax( Abc_Ntk_t * pNtk )
486 {
487 Abc_Obj_t * pNode;
488 int i, nFaninsMax = 0;
489 Abc_NtkForEachNode( pNtk, pNode, i )
490 {
491 if ( nFaninsMax < Abc_ObjFaninNum(pNode) )
492 nFaninsMax = Abc_ObjFaninNum(pNode);
493 }
494 return nFaninsMax;
495 }
Abc_NtkGetFanoutMax(Abc_Ntk_t * pNtk)496 int Abc_NtkGetFanoutMax( Abc_Ntk_t * pNtk )
497 {
498 Abc_Obj_t * pNode;
499 int i, nFaninsMax = 0;
500 Abc_NtkForEachNode( pNtk, pNode, i )
501 {
502 if ( nFaninsMax < Abc_ObjFanoutNum(pNode) )
503 nFaninsMax = Abc_ObjFanoutNum(pNode);
504 }
505 return nFaninsMax;
506 }
507
508 /**Function*************************************************************
509
510 Synopsis [Reads the total number of all fanins.]
511
512 Description []
513
514 SideEffects []
515
516 SeeAlso []
517
518 ***********************************************************************/
Abc_NtkGetTotalFanins(Abc_Ntk_t * pNtk)519 int Abc_NtkGetTotalFanins( Abc_Ntk_t * pNtk )
520 {
521 Abc_Obj_t * pNode;
522 int i, nFanins = 0;
523 Abc_NtkForEachNode( pNtk, pNode, i )
524 nFanins += Abc_ObjFaninNum(pNode);
525 return nFanins;
526 }
527
528 /**Function*************************************************************
529
530 Synopsis [Cleans the copy field of all objects.]
531
532 Description []
533
534 SideEffects []
535
536 SeeAlso []
537
538 ***********************************************************************/
Abc_NtkCleanCopy(Abc_Ntk_t * pNtk)539 void Abc_NtkCleanCopy( Abc_Ntk_t * pNtk )
540 {
541 Abc_Obj_t * pObj;
542 int i;
543 Abc_NtkForEachObj( pNtk, pObj, i )
544 pObj->pCopy = NULL;
545 }
Abc_NtkCleanCopy_rec(Abc_Ntk_t * pNtk)546 void Abc_NtkCleanCopy_rec( Abc_Ntk_t * pNtk )
547 {
548 Abc_Obj_t * pObj;
549 int i;
550 Abc_NtkCleanCopy( pNtk );
551 Abc_NtkForEachBox( pNtk, pObj, i )
552 Abc_NtkCleanCopy_rec( Abc_ObjModel(pObj) );
553 }
554
555 /**Function*************************************************************
556
557 Synopsis [Cleans the copy field of all objects.]
558
559 Description []
560
561 SideEffects []
562
563 SeeAlso []
564
565 ***********************************************************************/
Abc_NtkCleanData(Abc_Ntk_t * pNtk)566 void Abc_NtkCleanData( Abc_Ntk_t * pNtk )
567 {
568 Abc_Obj_t * pObj;
569 int i;
570 Abc_NtkForEachObj( pNtk, pObj, i )
571 pObj->pData = NULL;
572 }
573
574 /**Function*************************************************************
575
576 Synopsis [Cleans the copy field of all objects.]
577
578 Description []
579
580 SideEffects []
581
582 SeeAlso []
583
584 ***********************************************************************/
Abc_NtkFillTemp(Abc_Ntk_t * pNtk)585 void Abc_NtkFillTemp( Abc_Ntk_t * pNtk )
586 {
587 Abc_Obj_t * pObj;
588 int i;
589 Abc_NtkForEachObj( pNtk, pObj, i )
590 pObj->iTemp = -1;
591 }
592
593 /**Function*************************************************************
594
595 Synopsis [Counts the number of nodes having non-trivial copies.]
596
597 Description []
598
599 SideEffects []
600
601 SeeAlso []
602
603 ***********************************************************************/
Abc_NtkCountCopy(Abc_Ntk_t * pNtk)604 int Abc_NtkCountCopy( Abc_Ntk_t * pNtk )
605 {
606 Abc_Obj_t * pObj;
607 int i, Counter = 0;
608 Abc_NtkForEachObj( pNtk, pObj, i )
609 {
610 if ( Abc_ObjIsNode(pObj) )
611 Counter += (pObj->pCopy != NULL);
612 }
613 return Counter;
614 }
615
616 /**Function*************************************************************
617
618 Synopsis [Saves copy field of the objects.]
619
620 Description []
621
622 SideEffects []
623
624 SeeAlso []
625
626 ***********************************************************************/
Abc_NtkSaveCopy(Abc_Ntk_t * pNtk)627 Vec_Ptr_t * Abc_NtkSaveCopy( Abc_Ntk_t * pNtk )
628 {
629 Vec_Ptr_t * vCopies;
630 Abc_Obj_t * pObj;
631 int i;
632 vCopies = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
633 Abc_NtkForEachObj( pNtk, pObj, i )
634 Vec_PtrWriteEntry( vCopies, i, pObj->pCopy );
635 return vCopies;
636 }
637
638 /**Function*************************************************************
639
640 Synopsis [Loads copy field of the objects.]
641
642 Description []
643
644 SideEffects []
645
646 SeeAlso []
647
648 ***********************************************************************/
Abc_NtkLoadCopy(Abc_Ntk_t * pNtk,Vec_Ptr_t * vCopies)649 void Abc_NtkLoadCopy( Abc_Ntk_t * pNtk, Vec_Ptr_t * vCopies )
650 {
651 Abc_Obj_t * pObj;
652 int i;
653 Abc_NtkForEachObj( pNtk, pObj, i )
654 pObj->pCopy = (Abc_Obj_t *)Vec_PtrEntry( vCopies, i );
655 }
656
657 /**Function*************************************************************
658
659 Synopsis [Cleans the copy field of all objects.]
660
661 Description []
662
663 SideEffects []
664
665 SeeAlso []
666
667 ***********************************************************************/
Abc_NtkCleanNext(Abc_Ntk_t * pNtk)668 void Abc_NtkCleanNext( Abc_Ntk_t * pNtk )
669 {
670 Abc_Obj_t * pObj;
671 int i;
672 Abc_NtkForEachObj( pNtk, pObj, i )
673 pObj->pNext = NULL;
674 }
Abc_NtkCleanNext_rec(Abc_Ntk_t * pNtk)675 void Abc_NtkCleanNext_rec( Abc_Ntk_t * pNtk )
676 {
677 Abc_Obj_t * pObj;
678 int i;
679 Abc_NtkCleanNext( pNtk );
680 Abc_NtkForEachBox( pNtk, pObj, i )
681 Abc_NtkCleanNext_rec( Abc_ObjModel(pObj) );
682 }
683
684 /**Function*************************************************************
685
686 Synopsis [Cleans the copy field of all objects.]
687
688 Description []
689
690 SideEffects []
691
692 SeeAlso []
693
694 ***********************************************************************/
Abc_NtkCleanMarkA(Abc_Ntk_t * pNtk)695 void Abc_NtkCleanMarkA( Abc_Ntk_t * pNtk )
696 {
697 Abc_Obj_t * pObj;
698 int i;
699 Abc_NtkForEachObj( pNtk, pObj, i )
700 pObj->fMarkA = 0;
701 }
702
703 /**Function*************************************************************
704
705 Synopsis [Cleans the copy field of all objects.]
706
707 Description []
708
709 SideEffects []
710
711 SeeAlso []
712
713 ***********************************************************************/
Abc_NtkCleanMarkB(Abc_Ntk_t * pNtk)714 void Abc_NtkCleanMarkB( Abc_Ntk_t * pNtk )
715 {
716 Abc_Obj_t * pObj;
717 int i;
718 Abc_NtkForEachObj( pNtk, pObj, i )
719 pObj->fMarkB = 0;
720 }
721
722 /**Function*************************************************************
723
724 Synopsis [Cleans the copy field of all objects.]
725
726 Description []
727
728 SideEffects []
729
730 SeeAlso []
731
732 ***********************************************************************/
Abc_NtkCleanMarkC(Abc_Ntk_t * pNtk)733 void Abc_NtkCleanMarkC( Abc_Ntk_t * pNtk )
734 {
735 Abc_Obj_t * pObj;
736 int i;
737 Abc_NtkForEachObj( pNtk, pObj, i )
738 pObj->fMarkC = 0;
739 }
740
741 /**Function*************************************************************
742
743 Synopsis [Cleans the copy field of all objects.]
744
745 Description []
746
747 SideEffects []
748
749 SeeAlso []
750
751 ***********************************************************************/
Abc_NtkCleanMarkAB(Abc_Ntk_t * pNtk)752 void Abc_NtkCleanMarkAB( Abc_Ntk_t * pNtk )
753 {
754 Abc_Obj_t * pObj;
755 int i;
756 Abc_NtkForEachObj( pNtk, pObj, i )
757 pObj->fMarkA = pObj->fMarkB = 0;
758 }
759
760 /**Function*************************************************************
761
762 Synopsis [Cleans the copy field of all objects.]
763
764 Description []
765
766 SideEffects []
767
768 SeeAlso []
769
770 ***********************************************************************/
Abc_NtkCleanMarkABC(Abc_Ntk_t * pNtk)771 void Abc_NtkCleanMarkABC( Abc_Ntk_t * pNtk )
772 {
773 Abc_Obj_t * pObj;
774 int i;
775 Abc_NtkForEachObj( pNtk, pObj, i )
776 pObj->fMarkA = pObj->fMarkB = pObj->fMarkC = 0;
777 }
778
779 /**Function*************************************************************
780
781 Synopsis [Returns the index of the given fanin.]
782
783 Description []
784
785 SideEffects []
786
787 SeeAlso []
788
789 ***********************************************************************/
Abc_NodeFindFanin(Abc_Obj_t * pNode,Abc_Obj_t * pFanin)790 int Abc_NodeFindFanin( Abc_Obj_t * pNode, Abc_Obj_t * pFanin )
791 {
792 Abc_Obj_t * pThis;
793 int i;
794 Abc_ObjForEachFanin( pNode, pThis, i )
795 if ( pThis == pFanin )
796 return i;
797 return -1;
798 }
799
800 /**Function*************************************************************
801
802 Synopsis [Checks if the internal node has CO fanout.]
803
804 Description []
805
806 SideEffects []
807
808 SeeAlso []
809
810 ***********************************************************************/
Abc_NodeFindCoFanout(Abc_Obj_t * pNode)811 Abc_Obj_t * Abc_NodeFindCoFanout( Abc_Obj_t * pNode )
812 {
813 Abc_Obj_t * pFanout;
814 int i;
815 Abc_ObjForEachFanout( pNode, pFanout, i )
816 if ( Abc_ObjIsCo(pFanout) )
817 return pFanout;
818 return NULL;
819 }
820
821 /**Function*************************************************************
822
823 Synopsis [Checks if the internal node has CO fanout.]
824
825 Description []
826
827 SideEffects []
828
829 SeeAlso []
830
831 ***********************************************************************/
Abc_NodeFindNonCoFanout(Abc_Obj_t * pNode)832 Abc_Obj_t * Abc_NodeFindNonCoFanout( Abc_Obj_t * pNode )
833 {
834 Abc_Obj_t * pFanout;
835 int i;
836 Abc_ObjForEachFanout( pNode, pFanout, i )
837 if ( !Abc_ObjIsCo(pFanout) )
838 return pFanout;
839 return NULL;
840 }
841
842 /**Function*************************************************************
843
844 Synopsis [Checks if the internal node has CO drivers with the same name.]
845
846 Description [Checks if the internal node can borrow its name from CO fanouts.
847 This is possible if all COs with non-complemented fanin edge pointing to this
848 node have the same name.]
849
850 SideEffects []
851
852 SeeAlso []
853
854 ***********************************************************************/
Abc_NodeHasUniqueCoFanout(Abc_Obj_t * pNode)855 Abc_Obj_t * Abc_NodeHasUniqueCoFanout( Abc_Obj_t * pNode )
856 {
857 Abc_Obj_t * pFanout, * pFanoutCo;
858 int i;
859 pFanoutCo = NULL;
860 Abc_ObjForEachFanout( pNode, pFanout, i )
861 {
862 if ( !Abc_ObjIsCo(pFanout) )
863 continue;
864 if ( Abc_ObjFaninC0(pFanout) )
865 continue;
866 if ( pFanoutCo == NULL )
867 {
868 assert( Abc_ObjFaninNum(pFanout) == 1 );
869 assert( Abc_ObjFanin0(pFanout) == pNode );
870 pFanoutCo = pFanout;
871 continue;
872 }
873 if ( strcmp( Abc_ObjName(pFanoutCo), Abc_ObjName(pFanout) ) ) // they have diff names
874 return NULL;
875 }
876 return pFanoutCo;
877 }
878
879 /**Function*************************************************************
880
881 Synopsis [Fixes the CO driver problem.]
882
883 Description []
884
885 SideEffects []
886
887 SeeAlso []
888
889 ***********************************************************************/
Abc_NtkFixCoDriverProblem(Abc_Obj_t * pDriver,Abc_Obj_t * pNodeCo,int fDuplicate)890 void Abc_NtkFixCoDriverProblem( Abc_Obj_t * pDriver, Abc_Obj_t * pNodeCo, int fDuplicate )
891 {
892 Abc_Ntk_t * pNtk = pDriver->pNtk;
893 Abc_Obj_t * pDriverNew, * pFanin;
894 int k;
895 if ( fDuplicate && !Abc_ObjIsCi(pDriver) )
896 {
897 pDriverNew = Abc_NtkDupObj( pNtk, pDriver, 0 );
898 Abc_ObjForEachFanin( pDriver, pFanin, k )
899 Abc_ObjAddFanin( pDriverNew, pFanin );
900 if ( Abc_ObjFaninC0(pNodeCo) )
901 {
902 // change polarity of the duplicated driver
903 Abc_NodeComplement( pDriverNew );
904 Abc_ObjXorFaninC( pNodeCo, 0 );
905 }
906 }
907 else
908 {
909 // add inverters and buffers when necessary
910 if ( Abc_ObjFaninC0(pNodeCo) )
911 {
912 pDriverNew = Abc_NtkCreateNodeInv( pNtk, pDriver );
913 Abc_ObjXorFaninC( pNodeCo, 0 );
914 }
915 else
916 pDriverNew = Abc_NtkCreateNodeBuf( pNtk, pDriver );
917 }
918 // update the fanin of the PO node
919 Abc_ObjPatchFanin( pNodeCo, pDriver, pDriverNew );
920 assert( Abc_ObjFanoutNum(pDriverNew) == 1 );
921 // remove the old driver if it dangles
922 // (this happens when the duplicated driver had only one complemented fanout)
923 if ( Abc_ObjFanoutNum(pDriver) == 0 )
924 Abc_NtkDeleteObj( pDriver );
925 }
926
927 /**Function*************************************************************
928
929 Synopsis [Returns 1 if COs of a logic network are simple.]
930
931 Description [The COs of a logic network are simple under three conditions:
932 (1) The edge from CO to its driver is not complemented.
933 (2) If CI is a driver of a CO, they have the same name.]
934 (3) If two COs share the same driver, they have the same name.]
935
936 SideEffects []
937
938 SeeAlso []
939
940 ***********************************************************************/
Abc_NtkLogicHasSimpleCos(Abc_Ntk_t * pNtk)941 int Abc_NtkLogicHasSimpleCos( Abc_Ntk_t * pNtk )
942 {
943 Abc_Obj_t * pNode, * pDriver;
944 int i;
945 assert( Abc_NtkIsLogic(pNtk) );
946 Abc_NtkIncrementTravId( pNtk );
947 Abc_NtkForEachCo( pNtk, pNode, i )
948 {
949 // if the driver is complemented, this is an error
950 pDriver = Abc_ObjFanin0(pNode);
951 if ( Abc_ObjFaninC0(pNode) )
952 return 0;
953 // if the driver is a CI and has different name, this is an error
954 if ( Abc_ObjIsCi(pDriver) && strcmp(Abc_ObjName(pDriver), Abc_ObjName(pNode)) )
955 return 0;
956 // if the driver is visited for the first time, remember the CO name
957 if ( !Abc_NodeIsTravIdCurrent(pDriver) )
958 {
959 pDriver->pNext = (Abc_Obj_t *)Abc_ObjName(pNode);
960 Abc_NodeSetTravIdCurrent(pDriver);
961 continue;
962 }
963 // the driver has second CO - if they have different name, this is an error
964 if ( strcmp((char *)pDriver->pNext, Abc_ObjName(pNode)) ) // diff names
965 return 0;
966 }
967 return 1;
968 }
969
970 /**Function*************************************************************
971
972 Synopsis [Transforms the network to have simple COs.]
973
974 Description [The COs of a logic network are simple under three conditions:
975 (1) The edge from CO to its driver is not complemented.
976 (2) If CI is a driver of a CO, they have the same name.]
977 (3) If two COs share the same driver, they have the same name.
978 In some cases, such as FPGA mapping, we prevent the increase in delay
979 by duplicating the driver nodes, rather than adding invs/bufs.]
980
981 SideEffects []
982
983 SeeAlso []
984
985 ***********************************************************************/
Abc_NtkLogicMakeSimpleCos2(Abc_Ntk_t * pNtk,int fDuplicate)986 int Abc_NtkLogicMakeSimpleCos2( Abc_Ntk_t * pNtk, int fDuplicate )
987 {
988 Abc_Obj_t * pNode, * pDriver;
989 int i, nDupGates = 0;
990 assert( Abc_NtkIsLogic(pNtk) );
991 Abc_NtkIncrementTravId( pNtk );
992 Abc_NtkForEachCo( pNtk, pNode, i )
993 {
994 // if the driver is complemented, this is an error
995 pDriver = Abc_ObjFanin0(pNode);
996 if ( Abc_ObjFaninC0(pNode) )
997 {
998 Abc_NtkFixCoDriverProblem( pDriver, pNode, fDuplicate );
999 nDupGates++;
1000 continue;
1001 }
1002 // if the driver is a CI and has different name, this is an error
1003 if ( Abc_ObjIsCi(pDriver) && strcmp(Abc_ObjName(pDriver), Abc_ObjName(pNode)) )
1004 {
1005 Abc_NtkFixCoDriverProblem( pDriver, pNode, fDuplicate );
1006 nDupGates++;
1007 continue;
1008 }
1009 // if the driver is visited for the first time, remember the CO name
1010 if ( !Abc_NodeIsTravIdCurrent(pDriver) )
1011 {
1012 pDriver->pNext = (Abc_Obj_t *)Abc_ObjName(pNode);
1013 Abc_NodeSetTravIdCurrent(pDriver);
1014 continue;
1015 }
1016 // the driver has second CO - if they have different name, this is an error
1017 if ( strcmp((char *)pDriver->pNext, Abc_ObjName(pNode)) ) // diff names
1018 {
1019 Abc_NtkFixCoDriverProblem( pDriver, pNode, fDuplicate );
1020 nDupGates++;
1021 continue;
1022 }
1023 }
1024 assert( Abc_NtkLogicHasSimpleCos(pNtk) );
1025 return nDupGates;
1026 }
1027
1028
1029 /**Function*************************************************************
1030
1031 Synopsis [Transforms the network to have simple COs.]
1032
1033 Description []
1034
1035 SideEffects []
1036
1037 SeeAlso []
1038
1039 ***********************************************************************/
Abc_NtkLogicMakeSimpleCosTest(Abc_Ntk_t * pNtk,int fDuplicate)1040 void Abc_NtkLogicMakeSimpleCosTest( Abc_Ntk_t * pNtk, int fDuplicate )
1041 {
1042 int nObjs = Abc_NtkObjNumMax(pNtk);
1043 unsigned * pType = ABC_CALLOC( unsigned, nObjs );
1044 Abc_Obj_t * pNode;
1045 int i, Counts[4] = {0}, Consts[2] = {0}, Inputs[2] = {0};
1046 // collect info
1047 Abc_NtkForEachCo( pNtk, pNode, i )
1048 {
1049 if ( Abc_ObjFaninId0(pNode) == 0 )
1050 Consts[Abc_ObjFaninC0(pNode)]++;
1051 if ( Abc_ObjIsCi(Abc_ObjFanin0(pNode)) )
1052 Inputs[Abc_ObjFaninC0(pNode)]++;
1053 pType[Abc_ObjFaninId0(pNode)] |= (1 << Abc_ObjFaninC0(pNode));
1054 }
1055 // count the numbers
1056 for ( i = 0; i < nObjs; i++ )
1057 Counts[pType[i]]++;
1058 for ( i = 0; i < 4; i++ )
1059 printf( "%d = %d ", i, Counts[i] );
1060 for ( i = 0; i < 2; i++ )
1061 printf( "c%d = %d ", i, Consts[i] );
1062 for ( i = 0; i < 2; i++ )
1063 printf( "i%d = %d ", i, Inputs[i] );
1064 printf( "\n" );
1065 ABC_FREE( pType );
1066 }
1067
1068 /**Function*************************************************************
1069
1070 Synopsis [Transforms the network to have simple COs.]
1071
1072 Description []
1073
1074 SideEffects []
1075
1076 SeeAlso []
1077
1078 ***********************************************************************/
Abc_NtkLogicMakeSimpleCos(Abc_Ntk_t * pNtk,int fDuplicate)1079 int Abc_NtkLogicMakeSimpleCos( Abc_Ntk_t * pNtk, int fDuplicate )
1080 {
1081 int fAddBuffers = 1;
1082 Vec_Ptr_t * vDrivers, * vCoTerms;
1083 Abc_Obj_t * pNode, * pDriver, * pDriverNew, * pFanin;
1084 int i, k, LevelMax, nTotal = 0;
1085 assert( Abc_NtkIsLogic(pNtk) );
1086 LevelMax = Abc_NtkLevel(pNtk);
1087 // Abc_NtkLogicMakeSimpleCosTest( pNtk, fDuplicate );
1088
1089 // fix constant drivers
1090 Abc_NtkForEachCo( pNtk, pNode, i )
1091 {
1092 pDriver = Abc_ObjFanin0(pNode);
1093 if ( !Abc_NodeIsConst(pDriver) )
1094 continue;
1095 pDriverNew = (Abc_ObjFaninC0(pNode) == Abc_NodeIsConst0(pDriver)) ? Abc_NtkCreateNodeConst1(pNtk) : Abc_NtkCreateNodeConst0(pNtk);
1096 if ( Abc_ObjFaninC0(pNode) )
1097 Abc_ObjXorFaninC( pNode, 0 );
1098 Abc_ObjPatchFanin( pNode, pDriver, pDriverNew );
1099 if ( Abc_ObjFanoutNum(pDriver) == 0 )
1100 Abc_NtkDeleteObj( pDriver );
1101 }
1102
1103 // collect drivers pointed by complemented edges
1104 vDrivers = Vec_PtrAlloc( 100 );
1105 Abc_NtkIncrementTravId( pNtk );
1106 Abc_NtkForEachCo( pNtk, pNode, i )
1107 {
1108 if ( !Abc_ObjFaninC0(pNode) )
1109 continue;
1110 pDriver = Abc_ObjFanin0(pNode);
1111 if ( Abc_NodeIsTravIdCurrent(pDriver) )
1112 continue;
1113 Abc_NodeSetTravIdCurrent(pDriver);
1114 Vec_PtrPush( vDrivers, pDriver );
1115 }
1116 // fix complemented drivers
1117 if ( Vec_PtrSize(vDrivers) > 0 )
1118 {
1119 int nDupGates = 0, nDupInvs = 0, nDupChange = 0;
1120 Vec_Ptr_t * vFanouts = Vec_PtrAlloc( 100 );
1121 Vec_PtrForEachEntry( Abc_Obj_t *, vDrivers, pDriver, i )
1122 {
1123 int fHasDir = 0, fHasInv = 0, fHasOther = 0;
1124 Abc_ObjForEachFanout( pDriver, pNode, k )
1125 {
1126 if ( !Abc_ObjIsCo(pNode) )
1127 {
1128 assert( !Abc_ObjFaninC0(pNode) );
1129 fHasOther = 1;
1130 continue;
1131 }
1132 if ( Abc_ObjFaninC0(pNode) )
1133 fHasInv = 1;
1134 else //if ( Abc_ObjFaninC0(pNode) )
1135 fHasDir = 1;
1136 }
1137 assert( fHasInv );
1138 if ( Abc_ObjIsCi(pDriver) || fHasDir || (fHasOther && Abc_NtkHasMapping(pNtk)) ) // cannot change
1139 {
1140 // duplicate if critical
1141 if ( fDuplicate && Abc_ObjIsNode(pDriver) && Abc_ObjLevel(pDriver) == LevelMax )
1142 {
1143 pDriverNew = Abc_NtkDupObj( pNtk, pDriver, 0 );
1144 Abc_ObjForEachFanin( pDriver, pFanin, k )
1145 Abc_ObjAddFanin( pDriverNew, pFanin );
1146 Abc_NodeComplement( pDriverNew );
1147 nDupGates++;
1148 }
1149 else // add inverter
1150 {
1151 pDriverNew = Abc_NtkCreateNodeInv( pNtk, pDriver );
1152 nDupInvs++;
1153 }
1154 // collect CO fanouts to be redirected to the new node
1155 Vec_PtrClear( vFanouts );
1156 Abc_ObjForEachFanout( pDriver, pNode, k )
1157 if ( Abc_ObjIsCo(pNode) && Abc_ObjFaninC0(pNode) )
1158 Vec_PtrPush( vFanouts, pNode );
1159 assert( Vec_PtrSize(vFanouts) > 0 );
1160 Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pNode, k )
1161 {
1162 Abc_ObjXorFaninC( pNode, 0 );
1163 Abc_ObjPatchFanin( pNode, pDriver, pDriverNew );
1164 assert( Abc_ObjIsCi(pDriver) || Abc_ObjFanoutNum(pDriver) > 0 );
1165 }
1166 }
1167 else // can change
1168 {
1169 // change polarity of the driver
1170 assert( Abc_ObjIsNode(pDriver) );
1171 Abc_NodeComplement( pDriver );
1172 Abc_ObjForEachFanout( pDriver, pNode, k )
1173 {
1174 if ( Abc_ObjIsCo(pNode) )
1175 {
1176 assert( Abc_ObjFaninC0(pNode) );
1177 Abc_ObjXorFaninC( pNode, 0 );
1178 }
1179 else if ( Abc_ObjIsNode(pNode) )
1180 Abc_NodeComplementInput( pNode, pDriver );
1181 else assert( 0 );
1182 }
1183 nDupChange++;
1184 }
1185 }
1186 Vec_PtrFree( vFanouts );
1187 // printf( "Resolving inverted CO drivers: Invs = %d. Dups = %d. Changes = %d.\n",
1188 // nDupInvs, nDupGates, nDupChange );
1189 nTotal += nDupInvs + nDupGates;
1190 }
1191 Vec_PtrFree( vDrivers );
1192
1193 // collect COs that needs fixing by adding buffers or duplicating
1194 vCoTerms = Vec_PtrAlloc( 100 );
1195 Abc_NtkIncrementTravId( pNtk );
1196
1197 // The following cases should be addressed only if the network is written
1198 // into a BLIF file. Otherwise, it is possible to skip them:
1199 // (1) if a CO points to a CI with a different name
1200 // (2) if an internal node drives more than one CO
1201 if ( fAddBuffers )
1202 Abc_NtkForEachCo( pNtk, pNode, i )
1203 {
1204 // if the driver is a CI and has different name, this is an error
1205 pDriver = Abc_ObjFanin0(pNode);
1206 if ( Abc_ObjIsCi(pDriver) && strcmp(Abc_ObjName(pDriver), Abc_ObjName(pNode)) )
1207 {
1208 Vec_PtrPush( vCoTerms, pNode );
1209 continue;
1210 }
1211 // if the driver is visited for the first time, remember the CO name
1212 if ( !Abc_NodeIsTravIdCurrent(pDriver) )
1213 {
1214 pDriver->pNext = (Abc_Obj_t *)Abc_ObjName(pNode);
1215 Abc_NodeSetTravIdCurrent(pDriver);
1216 continue;
1217 }
1218 // the driver has second CO - if they have different name, this is an error
1219 if ( strcmp((char *)pDriver->pNext, Abc_ObjName(pNode)) ) // diff names
1220 {
1221 Vec_PtrPush( vCoTerms, pNode );
1222 continue;
1223 }
1224 }
1225 // fix duplication problem
1226 if ( Vec_PtrSize(vCoTerms) > 0 )
1227 {
1228 int nDupBufs = 0, nDupGates = 0;
1229 Vec_PtrForEachEntry( Abc_Obj_t *, vCoTerms, pNode, i )
1230 {
1231 pDriver = Abc_ObjFanin0(pNode);
1232 // duplicate if critical
1233 if ( fDuplicate && Abc_ObjIsNode(pDriver) && (Abc_NtkHasMapping(pNtk) || Abc_ObjLevel(pDriver) == LevelMax) )
1234 {
1235 pDriverNew = Abc_NtkDupObj( pNtk, pDriver, 0 );
1236 Abc_ObjForEachFanin( pDriver, pFanin, k )
1237 Abc_ObjAddFanin( pDriverNew, pFanin );
1238 nDupGates++;
1239 }
1240 else // add buffer
1241 {
1242 pDriverNew = Abc_NtkCreateNodeBuf( pNtk, pDriver );
1243 Abc_ObjAssignName( pDriverNew, Abc_ObjName(pDriver), "_buf" );
1244 nDupBufs++;
1245 }
1246 // swing the PO
1247 Abc_ObjPatchFanin( pNode, pDriver, pDriverNew );
1248 assert( Abc_ObjIsCi(pDriver) || Abc_ObjFanoutNum(pDriver) > 0 );
1249 }
1250 // printf( "Resolving shared CO drivers: Bufs = %d. Dups = %d.\n", nDupBufs, nDupGates );
1251 nTotal += nDupBufs + nDupGates;
1252 }
1253 Vec_PtrFree( vCoTerms );
1254 return nTotal;
1255 }
1256
1257 /**Function*************************************************************
1258
1259 Synopsis [Inserts a new node in the order by levels.]
1260
1261 Description []
1262
1263 SideEffects []
1264
1265 SeeAlso []
1266
1267 ***********************************************************************/
Abc_VecObjPushUniqueOrderByLevel(Vec_Ptr_t * p,Abc_Obj_t * pNode)1268 void Abc_VecObjPushUniqueOrderByLevel( Vec_Ptr_t * p, Abc_Obj_t * pNode )
1269 {
1270 Abc_Obj_t * pNode1, * pNode2;
1271 int i;
1272 if ( Vec_PtrPushUnique(p, pNode) )
1273 return;
1274 // find the p of the node
1275 for ( i = p->nSize-1; i > 0; i-- )
1276 {
1277 pNode1 = (Abc_Obj_t *)p->pArray[i ];
1278 pNode2 = (Abc_Obj_t *)p->pArray[i-1];
1279 if ( Abc_ObjRegular(pNode1)->Level <= Abc_ObjRegular(pNode2)->Level )
1280 break;
1281 p->pArray[i ] = pNode2;
1282 p->pArray[i-1] = pNode1;
1283 }
1284 }
1285
1286
1287
1288 /**Function*************************************************************
1289
1290 Synopsis [Returns 1 if the node is the root of EXOR/NEXOR.]
1291
1292 Description []
1293
1294 SideEffects []
1295
1296 SeeAlso []
1297
1298 ***********************************************************************/
Abc_NodeIsExorType(Abc_Obj_t * pNode)1299 int Abc_NodeIsExorType( Abc_Obj_t * pNode )
1300 {
1301 Abc_Obj_t * pNode0, * pNode1;
1302 // check that the node is regular
1303 assert( !Abc_ObjIsComplement(pNode) );
1304 // if the node is not AND, this is not EXOR
1305 if ( !Abc_AigNodeIsAnd(pNode) )
1306 return 0;
1307 // if the children are not complemented, this is not EXOR
1308 if ( !Abc_ObjFaninC0(pNode) || !Abc_ObjFaninC1(pNode) )
1309 return 0;
1310 // get children
1311 pNode0 = Abc_ObjFanin0(pNode);
1312 pNode1 = Abc_ObjFanin1(pNode);
1313 // if the children are not ANDs, this is not EXOR
1314 if ( Abc_ObjFaninNum(pNode0) != 2 || Abc_ObjFaninNum(pNode1) != 2 )
1315 return 0;
1316 // this is AIG, which means the fanins should be ordered
1317 assert( Abc_ObjFaninId0(pNode0) != Abc_ObjFaninId1(pNode1) ||
1318 Abc_ObjFaninId0(pNode1) != Abc_ObjFaninId1(pNode0) );
1319 // if grand children are not the same, this is not EXOR
1320 if ( Abc_ObjFaninId0(pNode0) != Abc_ObjFaninId0(pNode1) ||
1321 Abc_ObjFaninId1(pNode0) != Abc_ObjFaninId1(pNode1) )
1322 return 0;
1323 // finally, if the complemented edges are matched, this is not EXOR
1324 if ( Abc_ObjFaninC0(pNode0) == Abc_ObjFaninC0(pNode1) ||
1325 Abc_ObjFaninC1(pNode0) == Abc_ObjFaninC1(pNode1) )
1326 return 0;
1327 return 1;
1328 }
1329
1330 /**Function*************************************************************
1331
1332 Synopsis [Returns 1 if the node is the root of MUX or EXOR/NEXOR.]
1333
1334 Description []
1335
1336 SideEffects []
1337
1338 SeeAlso []
1339
1340 ***********************************************************************/
Abc_NodeIsMuxType(Abc_Obj_t * pNode)1341 int Abc_NodeIsMuxType( Abc_Obj_t * pNode )
1342 {
1343 Abc_Obj_t * pNode0, * pNode1;
1344 // check that the node is regular
1345 assert( !Abc_ObjIsComplement(pNode) );
1346 // if the node is not AND, this is not MUX
1347 if ( !Abc_AigNodeIsAnd(pNode) )
1348 return 0;
1349 // if the children are not complemented, this is not MUX
1350 if ( !Abc_ObjFaninC0(pNode) || !Abc_ObjFaninC1(pNode) )
1351 return 0;
1352 // get children
1353 pNode0 = Abc_ObjFanin0(pNode);
1354 pNode1 = Abc_ObjFanin1(pNode);
1355 // if the children are not ANDs, this is not MUX
1356 if ( !Abc_AigNodeIsAnd(pNode0) || !Abc_AigNodeIsAnd(pNode1) )
1357 return 0;
1358 // otherwise the node is MUX iff it has a pair of equal grandchildren with opposite polarity
1359 return (Abc_ObjFaninId0(pNode0) == Abc_ObjFaninId0(pNode1) && (Abc_ObjFaninC0(pNode0) ^ Abc_ObjFaninC0(pNode1))) ||
1360 (Abc_ObjFaninId0(pNode0) == Abc_ObjFaninId1(pNode1) && (Abc_ObjFaninC0(pNode0) ^ Abc_ObjFaninC1(pNode1))) ||
1361 (Abc_ObjFaninId1(pNode0) == Abc_ObjFaninId0(pNode1) && (Abc_ObjFaninC1(pNode0) ^ Abc_ObjFaninC0(pNode1))) ||
1362 (Abc_ObjFaninId1(pNode0) == Abc_ObjFaninId1(pNode1) && (Abc_ObjFaninC1(pNode0) ^ Abc_ObjFaninC1(pNode1)));
1363 }
1364
1365 /**Function*************************************************************
1366
1367 Synopsis [Returns 1 if the node is the root of MUX or EXOR/NEXOR.]
1368
1369 Description []
1370
1371 SideEffects []
1372
1373 SeeAlso []
1374
1375 ***********************************************************************/
Abc_NtkCountMuxes(Abc_Ntk_t * pNtk)1376 int Abc_NtkCountMuxes( Abc_Ntk_t * pNtk )
1377 {
1378 Abc_Obj_t * pNode;
1379 int i;
1380 int Counter = 0;
1381 Abc_NtkForEachNode( pNtk, pNode, i )
1382 Counter += Abc_NodeIsMuxType( pNode );
1383 return Counter;
1384 }
1385
1386 /**Function*************************************************************
1387
1388 Synopsis [Returns 1 if the node is the control type of the MUX.]
1389
1390 Description []
1391
1392 SideEffects []
1393
1394 SeeAlso []
1395
1396 ***********************************************************************/
Abc_NodeIsMuxControlType(Abc_Obj_t * pNode)1397 int Abc_NodeIsMuxControlType( Abc_Obj_t * pNode )
1398 {
1399 Abc_Obj_t * pNode0, * pNode1;
1400 // check that the node is regular
1401 assert( !Abc_ObjIsComplement(pNode) );
1402 // skip the node that do not have two fanouts
1403 if ( Abc_ObjFanoutNum(pNode) != 2 )
1404 return 0;
1405 // get the fanouts
1406 pNode0 = Abc_ObjFanout( pNode, 0 );
1407 pNode1 = Abc_ObjFanout( pNode, 1 );
1408 // if they have more than one fanout, we are not interested
1409 if ( Abc_ObjFanoutNum(pNode0) != 1 || Abc_ObjFanoutNum(pNode1) != 1 )
1410 return 0;
1411 // if the fanouts have the same fanout, this is MUX or EXOR (or a redundant gate (CA)(CB))
1412 return Abc_ObjFanout0(pNode0) == Abc_ObjFanout0(pNode1);
1413 }
1414
1415 /**Function*************************************************************
1416
1417 Synopsis [Recognizes what nodes are control and data inputs of a MUX.]
1418
1419 Description [If the node is a MUX, returns the control variable C.
1420 Assigns nodes T and E to be the then and else variables of the MUX.
1421 Node C is never complemented. Nodes T and E can be complemented.
1422 This function also recognizes EXOR/NEXOR gates as MUXes.]
1423
1424 SideEffects []
1425
1426 SeeAlso []
1427
1428 ***********************************************************************/
Abc_NodeRecognizeMux(Abc_Obj_t * pNode,Abc_Obj_t ** ppNodeT,Abc_Obj_t ** ppNodeE)1429 Abc_Obj_t * Abc_NodeRecognizeMux( Abc_Obj_t * pNode, Abc_Obj_t ** ppNodeT, Abc_Obj_t ** ppNodeE )
1430 {
1431 Abc_Obj_t * pNode0, * pNode1;
1432 assert( !Abc_ObjIsComplement(pNode) );
1433 assert( Abc_NodeIsMuxType(pNode) );
1434 // get children
1435 pNode0 = Abc_ObjFanin0(pNode);
1436 pNode1 = Abc_ObjFanin1(pNode);
1437 // find the control variable
1438 // if ( pNode1->p1 == Fraig_Not(pNode2->p1) )
1439 if ( Abc_ObjFaninId0(pNode0) == Abc_ObjFaninId0(pNode1) && (Abc_ObjFaninC0(pNode0) ^ Abc_ObjFaninC0(pNode1)) )
1440 {
1441 // if ( Fraig_IsComplement(pNode1->p1) )
1442 if ( Abc_ObjFaninC0(pNode0) )
1443 { // pNode2->p1 is positive phase of C
1444 *ppNodeT = Abc_ObjNot(Abc_ObjChild1(pNode1));//pNode2->p2);
1445 *ppNodeE = Abc_ObjNot(Abc_ObjChild1(pNode0));//pNode1->p2);
1446 return Abc_ObjChild0(pNode1);//pNode2->p1;
1447 }
1448 else
1449 { // pNode1->p1 is positive phase of C
1450 *ppNodeT = Abc_ObjNot(Abc_ObjChild1(pNode0));//pNode1->p2);
1451 *ppNodeE = Abc_ObjNot(Abc_ObjChild1(pNode1));//pNode2->p2);
1452 return Abc_ObjChild0(pNode0);//pNode1->p1;
1453 }
1454 }
1455 // else if ( pNode1->p1 == Fraig_Not(pNode2->p2) )
1456 else if ( Abc_ObjFaninId0(pNode0) == Abc_ObjFaninId1(pNode1) && (Abc_ObjFaninC0(pNode0) ^ Abc_ObjFaninC1(pNode1)) )
1457 {
1458 // if ( Fraig_IsComplement(pNode1->p1) )
1459 if ( Abc_ObjFaninC0(pNode0) )
1460 { // pNode2->p2 is positive phase of C
1461 *ppNodeT = Abc_ObjNot(Abc_ObjChild0(pNode1));//pNode2->p1);
1462 *ppNodeE = Abc_ObjNot(Abc_ObjChild1(pNode0));//pNode1->p2);
1463 return Abc_ObjChild1(pNode1);//pNode2->p2;
1464 }
1465 else
1466 { // pNode1->p1 is positive phase of C
1467 *ppNodeT = Abc_ObjNot(Abc_ObjChild1(pNode0));//pNode1->p2);
1468 *ppNodeE = Abc_ObjNot(Abc_ObjChild0(pNode1));//pNode2->p1);
1469 return Abc_ObjChild0(pNode0);//pNode1->p1;
1470 }
1471 }
1472 // else if ( pNode1->p2 == Fraig_Not(pNode2->p1) )
1473 else if ( Abc_ObjFaninId1(pNode0) == Abc_ObjFaninId0(pNode1) && (Abc_ObjFaninC1(pNode0) ^ Abc_ObjFaninC0(pNode1)) )
1474 {
1475 // if ( Fraig_IsComplement(pNode1->p2) )
1476 if ( Abc_ObjFaninC1(pNode0) )
1477 { // pNode2->p1 is positive phase of C
1478 *ppNodeT = Abc_ObjNot(Abc_ObjChild1(pNode1));//pNode2->p2);
1479 *ppNodeE = Abc_ObjNot(Abc_ObjChild0(pNode0));//pNode1->p1);
1480 return Abc_ObjChild0(pNode1);//pNode2->p1;
1481 }
1482 else
1483 { // pNode1->p2 is positive phase of C
1484 *ppNodeT = Abc_ObjNot(Abc_ObjChild0(pNode0));//pNode1->p1);
1485 *ppNodeE = Abc_ObjNot(Abc_ObjChild1(pNode1));//pNode2->p2);
1486 return Abc_ObjChild1(pNode0);//pNode1->p2;
1487 }
1488 }
1489 // else if ( pNode1->p2 == Fraig_Not(pNode2->p2) )
1490 else if ( Abc_ObjFaninId1(pNode0) == Abc_ObjFaninId1(pNode1) && (Abc_ObjFaninC1(pNode0) ^ Abc_ObjFaninC1(pNode1)) )
1491 {
1492 // if ( Fraig_IsComplement(pNode1->p2) )
1493 if ( Abc_ObjFaninC1(pNode0) )
1494 { // pNode2->p2 is positive phase of C
1495 *ppNodeT = Abc_ObjNot(Abc_ObjChild0(pNode1));//pNode2->p1);
1496 *ppNodeE = Abc_ObjNot(Abc_ObjChild0(pNode0));//pNode1->p1);
1497 return Abc_ObjChild1(pNode1);//pNode2->p2;
1498 }
1499 else
1500 { // pNode1->p2 is positive phase of C
1501 *ppNodeT = Abc_ObjNot(Abc_ObjChild0(pNode0));//pNode1->p1);
1502 *ppNodeE = Abc_ObjNot(Abc_ObjChild0(pNode1));//pNode2->p1);
1503 return Abc_ObjChild1(pNode0);//pNode1->p2;
1504 }
1505 }
1506 assert( 0 ); // this is not MUX
1507 return NULL;
1508 }
1509
1510 /**Function*************************************************************
1511
1512 Synopsis [Prepares two network for a two-argument command similar to "verify".]
1513
1514 Description []
1515
1516 SideEffects []
1517
1518 SeeAlso []
1519
1520 ***********************************************************************/
Abc_NtkPrepareTwoNtks(FILE * pErr,Abc_Ntk_t * pNtk,char ** argv,int argc,Abc_Ntk_t ** ppNtk1,Abc_Ntk_t ** ppNtk2,int * pfDelete1,int * pfDelete2,int fCheck)1521 int Abc_NtkPrepareTwoNtks( FILE * pErr, Abc_Ntk_t * pNtk, char ** argv, int argc,
1522 Abc_Ntk_t ** ppNtk1, Abc_Ntk_t ** ppNtk2, int * pfDelete1, int * pfDelete2, int fCheck )
1523 {
1524 FILE * pFile;
1525 Abc_Ntk_t * pNtk1, * pNtk2, * pNtkTemp;
1526 int util_optind = 0;
1527
1528 *pfDelete1 = 0;
1529 *pfDelete2 = 0;
1530 if ( argc == util_optind )
1531 { // use the spec
1532 if ( pNtk == NULL )
1533 {
1534 fprintf( pErr, "Empty current network.\n" );
1535 return 0;
1536 }
1537 if ( pNtk->pSpec == NULL )
1538 {
1539 fprintf( pErr, "The external spec is not given.\n" );
1540 return 0;
1541 }
1542 pFile = fopen( pNtk->pSpec, "r" );
1543 if ( pFile == NULL )
1544 {
1545 fprintf( pErr, "Cannot open the external spec file \"%s\".\n", pNtk->pSpec );
1546 return 0;
1547 }
1548 else
1549 fclose( pFile );
1550 pNtk1 = Abc_NtkDup(pNtk);
1551 pNtk2 = Io_Read( pNtk->pSpec, Io_ReadFileType(pNtk->pSpec), fCheck, 0 );
1552 if ( pNtk2 == NULL )
1553 return 0;
1554 *pfDelete1 = 1;
1555 *pfDelete2 = 1;
1556 }
1557 else if ( argc == util_optind + 1 )
1558 {
1559 if ( pNtk == NULL )
1560 {
1561 fprintf( pErr, "Empty current network.\n" );
1562 return 0;
1563 }
1564 pNtk1 = Abc_NtkDup(pNtk);
1565 pNtk2 = Io_Read( argv[util_optind], Io_ReadFileType(argv[util_optind]), fCheck, 0 );
1566 if ( pNtk2 == NULL )
1567 return 0;
1568 *pfDelete1 = 1;
1569 *pfDelete2 = 1;
1570 }
1571 else if ( argc == util_optind + 2 )
1572 {
1573 pNtk1 = Io_Read( argv[util_optind], Io_ReadFileType(argv[util_optind]), fCheck, 0 );
1574 if ( pNtk1 == NULL )
1575 return 0;
1576 pNtk2 = Io_Read( argv[util_optind+1], Io_ReadFileType(argv[util_optind+1]), fCheck, 0 );
1577 if ( pNtk2 == NULL )
1578 {
1579 Abc_NtkDelete( pNtk1 );
1580 return 0;
1581 }
1582 *pfDelete1 = 1;
1583 *pfDelete2 = 1;
1584 }
1585 else
1586 {
1587 fprintf( pErr, "Wrong number of arguments.\n" );
1588 return 0;
1589 }
1590
1591 // make sure the networks are strashed
1592 if ( !Abc_NtkIsStrash(pNtk1) )
1593 {
1594 pNtkTemp = Abc_NtkStrash( pNtk1, 0, 1, 0 );
1595 if ( *pfDelete1 )
1596 Abc_NtkDelete( pNtk1 );
1597 pNtk1 = pNtkTemp;
1598 *pfDelete1 = 1;
1599 }
1600 if ( !Abc_NtkIsStrash(pNtk2) )
1601 {
1602 pNtkTemp = Abc_NtkStrash( pNtk2, 0, 1, 0 );
1603 if ( *pfDelete2 )
1604 Abc_NtkDelete( pNtk2 );
1605 pNtk2 = pNtkTemp;
1606 *pfDelete2 = 1;
1607 }
1608
1609 *ppNtk1 = pNtk1;
1610 *ppNtk2 = pNtk2;
1611 return 1;
1612 }
1613
1614
1615 /**Function*************************************************************
1616
1617 Synopsis [Returns 1 if it is an AIG with choice nodes.]
1618
1619 Description []
1620
1621 SideEffects []
1622
1623 SeeAlso []
1624
1625 ***********************************************************************/
Abc_NodeCollectFanins(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)1626 void Abc_NodeCollectFanins( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
1627 {
1628 Abc_Obj_t * pFanin;
1629 int i;
1630 Vec_PtrClear(vNodes);
1631 Abc_ObjForEachFanin( pNode, pFanin, i )
1632 Vec_PtrPush( vNodes, pFanin );
1633 }
1634
1635 /**Function*************************************************************
1636
1637 Synopsis [Returns 1 if it is an AIG with choice nodes.]
1638
1639 Description []
1640
1641 SideEffects []
1642
1643 SeeAlso []
1644
1645 ***********************************************************************/
Abc_NodeCollectFanouts(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)1646 void Abc_NodeCollectFanouts( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
1647 {
1648 Abc_Obj_t * pFanout;
1649 int i;
1650 Vec_PtrClear(vNodes);
1651 Abc_ObjForEachFanout( pNode, pFanout, i )
1652 Vec_PtrPush( vNodes, pFanout );
1653 }
1654
1655 /**Function*************************************************************
1656
1657 Synopsis [Collects all latches in the network.]
1658
1659 Description []
1660
1661 SideEffects []
1662
1663 SeeAlso []
1664
1665 ***********************************************************************/
Abc_NtkCollectLatches(Abc_Ntk_t * pNtk)1666 Vec_Ptr_t * Abc_NtkCollectLatches( Abc_Ntk_t * pNtk )
1667 {
1668 Vec_Ptr_t * vLatches;
1669 Abc_Obj_t * pObj;
1670 int i;
1671 vLatches = Vec_PtrAlloc( 10 );
1672 Abc_NtkForEachObj( pNtk, pObj, i )
1673 Vec_PtrPush( vLatches, pObj );
1674 return vLatches;
1675 }
1676
1677 /**Function*************************************************************
1678
1679 Synopsis [Procedure used for sorting the nodes in increasing order of levels.]
1680
1681 Description []
1682
1683 SideEffects []
1684
1685 SeeAlso []
1686
1687 ***********************************************************************/
Abc_NodeCompareLevelsIncrease(Abc_Obj_t ** pp1,Abc_Obj_t ** pp2)1688 int Abc_NodeCompareLevelsIncrease( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 )
1689 {
1690 int Diff = Abc_ObjRegular(*pp1)->Level - Abc_ObjRegular(*pp2)->Level;
1691 if ( Diff < 0 )
1692 return -1;
1693 if ( Diff > 0 )
1694 return 1;
1695 Diff = Abc_ObjRegular(*pp1)->Id - Abc_ObjRegular(*pp2)->Id;
1696 if ( Diff < 0 )
1697 return -1;
1698 if ( Diff > 0 )
1699 return 1;
1700 return 0;
1701 }
1702
1703 /**Function*************************************************************
1704
1705 Synopsis [Procedure used for sorting the nodes in decreasing order of levels.]
1706
1707 Description []
1708
1709 SideEffects []
1710
1711 SeeAlso []
1712
1713 ***********************************************************************/
Abc_NodeCompareLevelsDecrease(Abc_Obj_t ** pp1,Abc_Obj_t ** pp2)1714 int Abc_NodeCompareLevelsDecrease( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 )
1715 {
1716 int Diff = Abc_ObjRegular(*pp1)->Level - Abc_ObjRegular(*pp2)->Level;
1717 if ( Diff > 0 )
1718 return -1;
1719 if ( Diff < 0 )
1720 return 1;
1721 Diff = Abc_ObjRegular(*pp1)->Id - Abc_ObjRegular(*pp2)->Id;
1722 if ( Diff > 0 )
1723 return -1;
1724 if ( Diff < 0 )
1725 return 1;
1726 return 0;
1727 }
1728
1729 /**Function*************************************************************
1730
1731 Synopsis [Creates the array of fanout counters.]
1732
1733 Description []
1734
1735 SideEffects []
1736
1737 SeeAlso []
1738
1739 ***********************************************************************/
Abc_NtkFanoutCounts(Abc_Ntk_t * pNtk)1740 Vec_Int_t * Abc_NtkFanoutCounts( Abc_Ntk_t * pNtk )
1741 {
1742 Vec_Int_t * vFanNums;
1743 Abc_Obj_t * pObj;
1744 int i;
1745 vFanNums = Vec_IntAlloc( 0 );
1746 Vec_IntFill( vFanNums, Abc_NtkObjNumMax(pNtk), -1 );
1747 Abc_NtkForEachObj( pNtk, pObj, i )
1748 if ( Abc_ObjIsCi(pObj) || Abc_ObjIsNode(pObj) )
1749 Vec_IntWriteEntry( vFanNums, i, Abc_ObjFanoutNum(pObj) );
1750 return vFanNums;
1751 }
1752
1753 /**Function*************************************************************
1754
1755 Synopsis [Collects all objects into one array.]
1756
1757 Description []
1758
1759 SideEffects []
1760
1761 SeeAlso []
1762
1763 ***********************************************************************/
Abc_NtkCollectObjects(Abc_Ntk_t * pNtk)1764 Vec_Ptr_t * Abc_NtkCollectObjects( Abc_Ntk_t * pNtk )
1765 {
1766 Vec_Ptr_t * vNodes;
1767 Abc_Obj_t * pNode;
1768 int i;
1769 vNodes = Vec_PtrAlloc( 100 );
1770 Abc_NtkForEachObj( pNtk, pNode, i )
1771 Vec_PtrPush( vNodes, pNode );
1772 return vNodes;
1773 }
1774
1775 /**Function*************************************************************
1776
1777 Synopsis [Returns the array of CI IDs.]
1778
1779 Description []
1780
1781 SideEffects []
1782
1783 SeeAlso []
1784
1785 ***********************************************************************/
Abc_NtkGetCiIds(Abc_Ntk_t * pNtk)1786 Vec_Int_t * Abc_NtkGetCiIds( Abc_Ntk_t * pNtk )
1787 {
1788 Vec_Int_t * vCiIds;
1789 Abc_Obj_t * pObj;
1790 int i;
1791 vCiIds = Vec_IntAlloc( Abc_NtkCiNum(pNtk) );
1792 Abc_NtkForEachCi( pNtk, pObj, i )
1793 Vec_IntPush( vCiIds, pObj->Id );
1794 return vCiIds;
1795 }
1796
1797 /**Function*************************************************************
1798
1799 Synopsis [Puts the nodes into the DFS order and reassign their IDs.]
1800
1801 Description []
1802
1803 SideEffects []
1804
1805 SeeAlso []
1806
1807 ***********************************************************************/
Abc_NtkReassignIds(Abc_Ntk_t * pNtk)1808 void Abc_NtkReassignIds( Abc_Ntk_t * pNtk )
1809 {
1810 Vec_Ptr_t * vNodes;
1811 Vec_Ptr_t * vObjsNew;
1812 Abc_Obj_t * pNode, * pTemp, * pConst1;
1813 int i, k;
1814 assert( Abc_NtkIsStrash(pNtk) );
1815 //printf( "Total = %d. Current = %d.\n", Abc_NtkObjNumMax(pNtk), Abc_NtkObjNum(pNtk) );
1816 // start the array of objects with new IDs
1817 vObjsNew = Vec_PtrAlloc( pNtk->nObjs );
1818 // put constant node first
1819 pConst1 = Abc_AigConst1(pNtk);
1820 assert( pConst1->Id == 0 );
1821 Vec_PtrPush( vObjsNew, pConst1 );
1822 // put PI nodes next
1823 Abc_NtkForEachPi( pNtk, pNode, i )
1824 {
1825 pNode->Id = Vec_PtrSize( vObjsNew );
1826 Vec_PtrPush( vObjsNew, pNode );
1827 }
1828 // put PO nodes next
1829 Abc_NtkForEachPo( pNtk, pNode, i )
1830 {
1831 pNode->Id = Vec_PtrSize( vObjsNew );
1832 Vec_PtrPush( vObjsNew, pNode );
1833 }
1834 // put latches and their inputs/outputs next
1835 Abc_NtkForEachBox( pNtk, pNode, i )
1836 {
1837 pNode->Id = Vec_PtrSize( vObjsNew );
1838 Vec_PtrPush( vObjsNew, pNode );
1839 Abc_ObjForEachFanin( pNode, pTemp, k )
1840 {
1841 pTemp->Id = Vec_PtrSize( vObjsNew );
1842 Vec_PtrPush( vObjsNew, pTemp );
1843 }
1844 Abc_ObjForEachFanout( pNode, pTemp, k )
1845 {
1846 pTemp->Id = Vec_PtrSize( vObjsNew );
1847 Vec_PtrPush( vObjsNew, pTemp );
1848 }
1849 }
1850 // finally, internal nodes in the DFS order
1851 vNodes = Abc_AigDfs( pNtk, 1, 0 );
1852 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
1853 {
1854 if ( pNode == pConst1 )
1855 continue;
1856 pNode->Id = Vec_PtrSize( vObjsNew );
1857 Vec_PtrPush( vObjsNew, pNode );
1858 }
1859 Vec_PtrFree( vNodes );
1860 assert( Vec_PtrSize(vObjsNew) == pNtk->nObjs );
1861
1862 // update the fanin/fanout arrays
1863 Abc_NtkForEachObj( pNtk, pNode, i )
1864 {
1865 Abc_ObjForEachFanin( pNode, pTemp, k )
1866 pNode->vFanins.pArray[k] = pTemp->Id;
1867 Abc_ObjForEachFanout( pNode, pTemp, k )
1868 pNode->vFanouts.pArray[k] = pTemp->Id;
1869 }
1870
1871 // replace the array of objs
1872 Vec_PtrFree( pNtk->vObjs );
1873 pNtk->vObjs = vObjsNew;
1874
1875 // rehash the AIG
1876 Abc_AigRehash( (Abc_Aig_t *)pNtk->pManFunc );
1877
1878 // update the name manager!!!
1879 }
1880
1881 /**Function*************************************************************
1882
1883 Synopsis [Detect cases when non-trivial FF matching is possible.]
1884
1885 Description []
1886
1887 SideEffects []
1888
1889 SeeAlso []
1890
1891 ***********************************************************************/
Abc_NtkDetectMatching(Abc_Ntk_t * pNtk)1892 void Abc_NtkDetectMatching( Abc_Ntk_t * pNtk )
1893 {
1894 /*
1895 Abc_Obj_t * pLatch, * pFanin;
1896 int i, nTFFs, nJKFFs;
1897 nTFFs = nJKFFs = 0;
1898 Abc_NtkForEachLatch( pNtk, pLatch, i )
1899 {
1900 pFanin = Abc_ObjFanin0(pLatch);
1901 if ( Abc_ObjFaninNum(pFanin) != 2 )
1902 continue;
1903 if ( Abc_NodeIsExorType(pLatch) )
1904 {
1905 if ( Abc_ObjFanin0(Abc_ObjFanin0(pFanin)) == pLatch ||
1906 Abc_ObjFanin1(Abc_ObjFanin0(pFanin)) == pLatch )
1907 nTFFs++;
1908 }
1909 if ( Abc_ObjFaninNum( Abc_ObjFanin0(pFanin) ) != 2 ||
1910 Abc_ObjFaninNum( Abc_ObjFanin1(pFanin) ) != 2 )
1911 continue;
1912
1913 if ( (Abc_ObjFanin0(Abc_ObjFanin0(pFanin)) == pLatch ||
1914 Abc_ObjFanin1(Abc_ObjFanin0(pFanin)) == pLatch) &&
1915 (Abc_ObjFanin0(Abc_ObjFanin1(pFanin)) == pLatch ||
1916 Abc_ObjFanin1(Abc_ObjFanin1(pFanin)) == pLatch) )
1917 {
1918 nJKFFs++;
1919 }
1920 }
1921 printf( "D = %6d. T = %6d. JK = %6d. (%6.2f %%)\n",
1922 Abc_NtkLatchNum(pNtk), nTFFs, nJKFFs, 100.0 * nJKFFs / Abc_NtkLatchNum(pNtk) );
1923 */
1924 }
1925
1926
1927 /**Function*************************************************************
1928
1929 Synopsis [Compares the pointers.]
1930
1931 Description []
1932
1933 SideEffects []
1934
1935 SeeAlso []
1936
1937 ***********************************************************************/
Abc_ObjPointerCompare(void ** pp1,void ** pp2)1938 int Abc_ObjPointerCompare( void ** pp1, void ** pp2 )
1939 {
1940 if ( *pp1 < *pp2 )
1941 return -1;
1942 if ( *pp1 > *pp2 )
1943 return 1;
1944 return 0;
1945 }
1946
1947 /**Function*************************************************************
1948
1949 Synopsis [Adjusts the copy pointers.]
1950
1951 Description [This procedure assumes that the network was transformed
1952 into another network, which was in turn transformed into yet another
1953 network. It makes the pCopy pointers of the original network point to
1954 the objects of the yet another network.]
1955
1956 SideEffects []
1957
1958 SeeAlso []
1959
1960 ***********************************************************************/
Abc_NtkTransferCopy(Abc_Ntk_t * pNtk)1961 void Abc_NtkTransferCopy( Abc_Ntk_t * pNtk )
1962 {
1963 Abc_Obj_t * pObj;
1964 int i;
1965 Abc_NtkForEachObj( pNtk, pObj, i )
1966 if ( !Abc_ObjIsNet(pObj) )
1967 pObj->pCopy = pObj->pCopy? Abc_ObjCopyCond(pObj->pCopy) : NULL;
1968 }
1969
1970
1971 /**Function*************************************************************
1972
1973 Synopsis [Increaments the cut counter.]
1974
1975 Description [Returns 1 if it becomes equal to the ref counter.]
1976
1977 SideEffects []
1978
1979 SeeAlso []
1980
1981 ***********************************************************************/
Abc_ObjCrossCutInc(Abc_Obj_t * pObj)1982 static inline int Abc_ObjCrossCutInc( Abc_Obj_t * pObj )
1983 {
1984 // pObj->pCopy = (void *)(((int)pObj->pCopy)++);
1985 int Value = (int)(ABC_PTRINT_T)pObj->pCopy;
1986 pObj->pCopy = (Abc_Obj_t *)(ABC_PTRINT_T)(Value + 1);
1987 return (int)(ABC_PTRINT_T)pObj->pCopy == Abc_ObjFanoutNum(pObj);
1988 }
1989
1990 /**Function*************************************************************
1991
1992 Synopsis [Computes cross-cut of the circuit.]
1993
1994 Description [Returns 1 if it is the last visit to the node.]
1995
1996 SideEffects []
1997
1998 SeeAlso []
1999
2000 ***********************************************************************/
Abc_NtkCrossCut_rec(Abc_Obj_t * pObj,int * pnCutSize,int * pnCutSizeMax)2001 int Abc_NtkCrossCut_rec( Abc_Obj_t * pObj, int * pnCutSize, int * pnCutSizeMax )
2002 {
2003 Abc_Obj_t * pFanin;
2004 int i, nDecrem = 0;
2005 int fReverse = 0;
2006 if ( Abc_ObjIsCi(pObj) )
2007 return 0;
2008 // if visited, increment visit counter
2009 if ( Abc_NodeIsTravIdCurrent( pObj ) )
2010 return Abc_ObjCrossCutInc( pObj );
2011 Abc_NodeSetTravIdCurrent( pObj );
2012 // visit the fanins
2013 if ( !Abc_ObjIsCi(pObj) )
2014 {
2015 if ( fReverse )
2016 {
2017 Abc_ObjForEachFanin( pObj, pFanin, i )
2018 {
2019 pFanin = Abc_ObjFanin( pObj, Abc_ObjFaninNum(pObj) - 1 - i );
2020 nDecrem += Abc_NtkCrossCut_rec( pFanin, pnCutSize, pnCutSizeMax );
2021 }
2022 }
2023 else
2024 {
2025 Abc_ObjForEachFanin( pObj, pFanin, i )
2026 nDecrem += Abc_NtkCrossCut_rec( pFanin, pnCutSize, pnCutSizeMax );
2027 }
2028 }
2029 // count the node
2030 (*pnCutSize)++;
2031 if ( *pnCutSizeMax < *pnCutSize )
2032 *pnCutSizeMax = *pnCutSize;
2033 (*pnCutSize) -= nDecrem;
2034 return Abc_ObjCrossCutInc( pObj );
2035 }
2036
2037 /**Function*************************************************************
2038
2039 Synopsis [Computes cross-cut of the circuit.]
2040
2041 Description []
2042
2043 SideEffects []
2044
2045 SeeAlso []
2046
2047 ***********************************************************************/
Abc_NtkCrossCut(Abc_Ntk_t * pNtk)2048 int Abc_NtkCrossCut( Abc_Ntk_t * pNtk )
2049 {
2050 Abc_Obj_t * pObj;
2051 int nCutSize = 0, nCutSizeMax = 0;
2052 int i;
2053 Abc_NtkCleanCopy( pNtk );
2054 Abc_NtkIncrementTravId( pNtk );
2055 Abc_NtkForEachCo( pNtk, pObj, i )
2056 {
2057 Abc_NtkCrossCut_rec( pObj, &nCutSize, &nCutSizeMax );
2058 nCutSize--;
2059 }
2060 assert( nCutSize == 0 );
2061 printf( "Max cross cut size = %6d. Ratio = %6.2f %%\n", nCutSizeMax, 100.0 * nCutSizeMax/Abc_NtkObjNum(pNtk) );
2062 return nCutSizeMax;
2063 }
2064
2065
2066 /**Function*************************************************************
2067
2068 Synopsis [Prints all 3-var functions.]
2069
2070 Description []
2071
2072 SideEffects []
2073
2074 SeeAlso []
2075
2076 ***********************************************************************/
Abc_NtkPrint256()2077 void Abc_NtkPrint256()
2078 {
2079 FILE * pFile;
2080 unsigned i;
2081 pFile = fopen( "4varfs.txt", "w" );
2082 for ( i = 1; i < (1<<16)-1; i++ )
2083 {
2084 fprintf( pFile, "read_truth " );
2085 Extra_PrintBinary( pFile, &i, 16 );
2086 fprintf( pFile, "; clp; st; w 1.blif; map; cec 1.blif\n" );
2087 }
2088 fclose( pFile );
2089 }
2090
2091
2092 static int * pSupps;
2093
2094 /**Function*************************************************************
2095
2096 Synopsis [Compares the supergates by their level.]
2097
2098 Description []
2099
2100 SideEffects []
2101
2102 SeeAlso []
2103
2104 ***********************************************************************/
Abc_NtkCompareConesCompare(int * pNum1,int * pNum2)2105 int Abc_NtkCompareConesCompare( int * pNum1, int * pNum2 )
2106 {
2107 if ( pSupps[*pNum1] > pSupps[*pNum2] )
2108 return -1;
2109 if ( pSupps[*pNum1] < pSupps[*pNum2] )
2110 return 1;
2111 return 0;
2112 }
2113
2114 /**Function*************************************************************
2115
2116 Synopsis [Analyze choice node support.]
2117
2118 Description []
2119
2120 SideEffects []
2121
2122 SeeAlso []
2123
2124 ***********************************************************************/
Abc_NtkCompareCones(Abc_Ntk_t * pNtk)2125 void Abc_NtkCompareCones( Abc_Ntk_t * pNtk )
2126 {
2127 Vec_Ptr_t * vSupp, * vNodes, * vReverse;
2128 Abc_Obj_t * pObj, * pTemp;
2129 int Iter, i, k, Counter, CounterCos, CounterCosNew;
2130 int * pPerms;
2131
2132 // sort COs by support size
2133 pPerms = ABC_ALLOC( int, Abc_NtkCoNum(pNtk) );
2134 pSupps = ABC_ALLOC( int, Abc_NtkCoNum(pNtk) );
2135 Abc_NtkForEachCo( pNtk, pObj, i )
2136 {
2137 pPerms[i] = i;
2138 vSupp = Abc_NtkNodeSupport( pNtk, &pObj, 1 );
2139 pSupps[i] = Vec_PtrSize(vSupp);
2140 Vec_PtrFree( vSupp );
2141 }
2142 qsort( (void *)pPerms, (size_t)Abc_NtkCoNum(pNtk), sizeof(int), (int (*)(const void *, const void *)) Abc_NtkCompareConesCompare );
2143
2144 // consider COs in this order
2145 Iter = 0;
2146 Abc_NtkForEachCo( pNtk, pObj, i )
2147 {
2148 pObj = Abc_NtkCo( pNtk, pPerms[i] );
2149 if ( pObj->fMarkA )
2150 continue;
2151 Iter++;
2152
2153 vSupp = Abc_NtkNodeSupport( pNtk, &pObj, 1 );
2154 vNodes = Abc_NtkDfsNodes( pNtk, &pObj, 1 );
2155 vReverse = Abc_NtkDfsReverseNodesContained( pNtk, (Abc_Obj_t **)Vec_PtrArray(vSupp), Vec_PtrSize(vSupp) );
2156 // count the number of nodes in the reverse cone
2157 Counter = 0;
2158 for ( k = 1; k < Vec_PtrSize(vReverse) - 1; k++ )
2159 for ( pTemp = (Abc_Obj_t *)Vec_PtrEntry(vReverse, k); pTemp; pTemp = (Abc_Obj_t *)pTemp->pCopy )
2160 Counter++;
2161 CounterCos = CounterCosNew = 0;
2162 for ( pTemp = (Abc_Obj_t *)Vec_PtrEntryLast(vReverse); pTemp; pTemp = (Abc_Obj_t *)pTemp->pCopy )
2163 {
2164 assert( Abc_ObjIsCo(pTemp) );
2165 CounterCos++;
2166 if ( pTemp->fMarkA == 0 )
2167 CounterCosNew++;
2168 pTemp->fMarkA = 1;
2169 }
2170 // print statistics
2171 printf( "%4d CO %5d : Supp = %5d. Lev = %3d. Cone = %5d. Rev = %5d. COs = %3d (%3d).\n",
2172 Iter, pPerms[i], Vec_PtrSize(vSupp), Abc_ObjLevel(Abc_ObjFanin0(pObj)), Vec_PtrSize(vNodes), Counter, CounterCos, CounterCosNew );
2173
2174 if ( Vec_PtrSize(vSupp) < 10 )
2175 {
2176 // free arrays
2177 Vec_PtrFree( vSupp );
2178 Vec_PtrFree( vNodes );
2179 Vec_PtrFree( vReverse );
2180 break;
2181 }
2182
2183 // free arrays
2184 Vec_PtrFree( vSupp );
2185 Vec_PtrFree( vNodes );
2186 Vec_PtrFree( vReverse );
2187
2188 }
2189 Abc_NtkForEachCo( pNtk, pObj, i )
2190 pObj->fMarkA = 0;
2191
2192 ABC_FREE( pPerms );
2193 ABC_FREE( pSupps );
2194 }
2195
2196 /**Function*************************************************************
2197
2198 Synopsis [Analyze choice node support.]
2199
2200 Description []
2201
2202 SideEffects []
2203
2204 SeeAlso []
2205
2206 ***********************************************************************/
Abc_NtkCompareSupports(Abc_Ntk_t * pNtk)2207 void Abc_NtkCompareSupports( Abc_Ntk_t * pNtk )
2208 {
2209 Vec_Ptr_t * vSupp;
2210 Abc_Obj_t * pObj, * pTemp;
2211 int i, nNodesOld;
2212 assert( Abc_NtkIsStrash(pNtk) );
2213 Abc_AigForEachAnd( pNtk, pObj, i )
2214 {
2215 if ( !Abc_AigNodeIsChoice(pObj) )
2216 continue;
2217
2218 vSupp = Abc_NtkNodeSupport( pNtk, &pObj, 1 );
2219 nNodesOld = Vec_PtrSize(vSupp);
2220 Vec_PtrFree( vSupp );
2221
2222 for ( pTemp = (Abc_Obj_t *)pObj->pData; pTemp; pTemp = (Abc_Obj_t *)pTemp->pData )
2223 {
2224 vSupp = Abc_NtkNodeSupport( pNtk, &pTemp, 1 );
2225 if ( nNodesOld != Vec_PtrSize(vSupp) )
2226 printf( "Choice orig = %3d Choice new = %3d\n", nNodesOld, Vec_PtrSize(vSupp) );
2227 Vec_PtrFree( vSupp );
2228 }
2229 }
2230 }
2231
2232 /**Function*************************************************************
2233
2234 Synopsis [Complements the constraint outputs.]
2235
2236 Description []
2237
2238 SideEffects []
2239
2240 SeeAlso []
2241
2242 ***********************************************************************/
Abc_NtkInvertConstraints(Abc_Ntk_t * pNtk)2243 void Abc_NtkInvertConstraints( Abc_Ntk_t * pNtk )
2244 {
2245 Abc_Obj_t * pObj;
2246 int i;
2247 if ( Abc_NtkConstrNum(pNtk) == 0 )
2248 return;
2249 Abc_NtkForEachPo( pNtk, pObj, i )
2250 {
2251 if ( i >= Abc_NtkPoNum(pNtk) - Abc_NtkConstrNum(pNtk) )
2252 Abc_ObjXorFaninC( pObj, 0 );
2253 }
2254 }
2255
2256 /**Function*************************************************************
2257
2258 Synopsis []
2259
2260 Description []
2261
2262 SideEffects []
2263
2264 SeeAlso []
2265
2266 ***********************************************************************/
Abc_NtkPrintCiLevels(Abc_Ntk_t * pNtk)2267 void Abc_NtkPrintCiLevels( Abc_Ntk_t * pNtk )
2268 {
2269 Abc_Obj_t * pObj;
2270 int i;
2271 Abc_NtkForEachCi( pNtk, pObj, i )
2272 printf( "%c=%d ", 'a'+i, pObj->Level );
2273 printf( "\n" );
2274 }
2275
2276
2277 /**Function*************************************************************
2278
2279 Synopsis [Returns 1 if all other fanouts of pFanin are below pNode.]
2280
2281 Description []
2282
2283 SideEffects []
2284
2285 SeeAlso []
2286
2287 ***********************************************************************/
Abc_NtkAddBuffsEval(Abc_Obj_t * pNode,Abc_Obj_t * pFanin)2288 int Abc_NtkAddBuffsEval( Abc_Obj_t * pNode, Abc_Obj_t * pFanin )
2289 {
2290 Abc_Obj_t * pFanout;
2291 int i;
2292 Abc_ObjForEachFanout( pFanin, pFanout, i )
2293 if ( pFanout != pNode && pFanout->Level >= pNode->Level )
2294 return 0;
2295 return 1;
2296 }
2297 /**Function*************************************************************
2298
2299 Synopsis [Returns 1 if there exist a fanout of pFanin higher than pNode.]
2300
2301 Description []
2302
2303 SideEffects []
2304
2305 SeeAlso []
2306
2307 ***********************************************************************/
Abc_NtkAddBuffsEval2(Abc_Obj_t * pNode,Abc_Obj_t * pFanin)2308 int Abc_NtkAddBuffsEval2( Abc_Obj_t * pNode, Abc_Obj_t * pFanin )
2309 {
2310 Abc_Obj_t * pFanout;
2311 int i;
2312 Abc_ObjForEachFanout( pFanin, pFanout, i )
2313 if ( pFanout != pNode && pFanout->Level > pNode->Level )
2314 return 1;
2315 return 0;
2316 }
2317
2318 /**Function*************************************************************
2319
2320 Synopsis []
2321
2322 Description []
2323
2324 SideEffects []
2325
2326 SeeAlso []
2327
2328 ***********************************************************************/
Abc_NtkAddBuffsOne(Vec_Ptr_t * vBuffs,Abc_Obj_t * pFanin,int Level,int nLevelMax)2329 Abc_Obj_t * Abc_NtkAddBuffsOne( Vec_Ptr_t * vBuffs, Abc_Obj_t * pFanin, int Level, int nLevelMax )
2330 {
2331 Abc_Obj_t * pBuffer;
2332 assert( Level - 1 >= Abc_ObjLevel(pFanin) );
2333 pBuffer = (Abc_Obj_t *)Vec_PtrEntry( vBuffs, Abc_ObjId(pFanin) * nLevelMax + Level );
2334 if ( pBuffer == NULL )
2335 {
2336 if ( Level - 1 == Abc_ObjLevel(pFanin) )
2337 pBuffer = pFanin;
2338 else
2339 pBuffer = Abc_NtkAddBuffsOne( vBuffs, pFanin, Level - 1, nLevelMax );
2340 pBuffer = Abc_NtkCreateNodeBuf( Abc_ObjNtk(pFanin), pBuffer );
2341 Vec_PtrWriteEntry( vBuffs, Abc_ObjId(pFanin) * nLevelMax + Level, pBuffer );
2342 }
2343 return pBuffer;
2344 }
Abc_NtkAddBuffsInt(Abc_Ntk_t * pNtkInit,int fReverse,int nImprove,int fVerbose)2345 Abc_Ntk_t * Abc_NtkAddBuffsInt( Abc_Ntk_t * pNtkInit, int fReverse, int nImprove, int fVerbose )
2346 {
2347 Vec_Ptr_t * vBuffs;
2348 Abc_Ntk_t * pNtk = Abc_NtkDup( pNtkInit );
2349 Abc_Obj_t * pObj, * pFanin, * pBuffer;
2350 int i, k, Iter, nLevelMax = Abc_NtkLevel( pNtk );
2351 Abc_NtkForEachCo( pNtk, pObj, i )
2352 pObj->Level = nLevelMax + 1;
2353 if ( fReverse )
2354 {
2355 Vec_Ptr_t * vNodes = Abc_NtkDfs( pNtk, 1 );
2356 assert( nLevelMax < (1<<18) );
2357 Vec_PtrForEachEntryReverse( Abc_Obj_t *, vNodes, pObj, i )
2358 {
2359 pObj->Level = (1<<18);
2360 Abc_ObjForEachFanout( pObj, pFanin, k )
2361 pObj->Level = Abc_MinInt( pFanin->Level - 1, pObj->Level );
2362 assert( pObj->Level > 0 );
2363 }
2364 Abc_NtkForEachCi( pNtk, pObj, i )
2365 pObj->Level = 0;
2366
2367 // move the nodes down one step at a time
2368 for ( Iter = 0; Iter < nImprove; Iter++ )
2369 {
2370 int Counter = 0, TotalGain = 0;
2371 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
2372 {
2373 int CountGain = -1;
2374 assert( pObj->Level > 0 );
2375 Abc_ObjForEachFanin( pObj, pFanin, k )
2376 {
2377 assert( pFanin->Level < pObj->Level );
2378 if ( pFanin->Level + 1 == pObj->Level )
2379 break;
2380 }
2381 if ( k < Abc_ObjFaninNum(pObj) ) // cannot move
2382 continue;
2383 Abc_ObjForEachFanin( pObj, pFanin, k )
2384 CountGain += Abc_NtkAddBuffsEval( pObj, pFanin );
2385 if ( CountGain >= 0 ) // can move
2386 {
2387 pObj->Level--;
2388 Counter++;
2389 TotalGain += CountGain;
2390 }
2391 }
2392 if ( fVerbose )
2393 printf( "Shifted %5d nodes down with total gain %5d.\n", Counter, TotalGain );
2394 if ( Counter == 0 )
2395 break;
2396 }
2397 Vec_PtrFree( vNodes );
2398 }
2399 else
2400 {
2401 // move the nodes up one step at a time
2402 Vec_Ptr_t * vNodes = Abc_NtkDfs( pNtk, 1 );
2403 for ( Iter = 0; Iter < nImprove; Iter++ )
2404 {
2405 int Counter = 0, TotalGain = 0;
2406 Vec_PtrForEachEntryReverse( Abc_Obj_t *, vNodes, pObj, i )
2407 {
2408 int CountGain = 1;
2409 assert( pObj->Level <= (unsigned)nLevelMax );
2410 Abc_ObjForEachFanout( pObj, pFanin, k )
2411 {
2412 assert( pFanin->Level > pObj->Level );
2413 if ( pFanin->Level == pObj->Level + 1 )
2414 break;
2415 }
2416 if ( k < Abc_ObjFanoutNum(pObj) ) // cannot move
2417 continue;
2418 Abc_ObjForEachFanin( pObj, pFanin, k )
2419 CountGain -= !Abc_NtkAddBuffsEval2( pObj, pFanin );
2420 if ( CountGain >= 0 ) // can move
2421 {
2422 pObj->Level++;
2423 Counter++;
2424 TotalGain += CountGain;
2425 }
2426 }
2427 if ( fVerbose )
2428 printf( "Shifted %5d nodes up with total gain %5d.\n", Counter, TotalGain );
2429 if ( Counter == 0 )
2430 break;
2431 }
2432 Vec_PtrFree( vNodes );
2433 }
2434 vBuffs = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) * (nLevelMax + 1) );
2435 Abc_NtkForEachObj( pNtk, pObj, i )
2436 {
2437 if ( i == Vec_PtrSize(vBuffs) / (nLevelMax + 1) )
2438 break;
2439 if ( !Abc_ObjIsNode(pObj) && !Abc_ObjIsCo(pObj) )
2440 continue;
2441 Abc_ObjForEachFanin( pObj, pFanin, k )
2442 {
2443 assert( Abc_ObjLevel(pObj) - 1 >= Abc_ObjLevel(pFanin) );
2444 if ( Abc_ObjLevel(pObj) - 1 == Abc_ObjLevel(pFanin) )
2445 continue;
2446 pBuffer = Abc_NtkAddBuffsOne( vBuffs, pFanin, Abc_ObjLevel(pObj) - 1, nLevelMax );
2447 Abc_ObjPatchFanin( pObj, pFanin, pBuffer );
2448 }
2449 }
2450 Vec_PtrFree( vBuffs );
2451 Abc_NtkForEachCo( pNtk, pObj, i )
2452 pObj->Level = 0;
2453 return pNtk;
2454 }
Abc_NtkAddBuffs(Abc_Ntk_t * pNtkInit,int fDirect,int fReverse,int nImprove,int fVerbose)2455 Abc_Ntk_t * Abc_NtkAddBuffs( Abc_Ntk_t * pNtkInit, int fDirect, int fReverse, int nImprove, int fVerbose )
2456 {
2457 Abc_Ntk_t * pNtkD, * pNtkR;
2458 if ( fDirect )
2459 return Abc_NtkAddBuffsInt( pNtkInit, 0, nImprove, fVerbose );
2460 if ( fReverse )
2461 return Abc_NtkAddBuffsInt( pNtkInit, 1, nImprove, fVerbose );
2462 pNtkD = Abc_NtkAddBuffsInt( pNtkInit, 0, nImprove, fVerbose );
2463 pNtkR = Abc_NtkAddBuffsInt( pNtkInit, 1, nImprove, fVerbose );
2464 if ( Abc_NtkNodeNum(pNtkD) < Abc_NtkNodeNum(pNtkR) )
2465 {
2466 Abc_NtkDelete( pNtkR );
2467 return pNtkD;
2468 }
2469 else
2470 {
2471 Abc_NtkDelete( pNtkD );
2472 return pNtkR;
2473 }
2474 }
2475
2476 /**Function*************************************************************
2477
2478 Synopsis [Computes max delay using log(n) delay model.]
2479
2480 Description []
2481
2482 SideEffects []
2483
2484 SeeAlso []
2485
2486 ***********************************************************************/
Abc_NtkComputeDelay(Abc_Ntk_t * pNtk)2487 float Abc_NtkComputeDelay( Abc_Ntk_t * pNtk )
2488 {
2489 static double GateDelays[20] = { 1.00, 1.00, 2.00, 2.58, 3.00, 3.32, 3.58, 3.81, 4.00, 4.17, 4.32, 4.46, 4.58, 4.70, 4.81, 4.91, 5.00, 5.09, 5.17, 5.25 };
2490 Vec_Ptr_t * vNodes;
2491 Abc_Obj_t * pObj, * pFanin;
2492 float DelayMax, Delays[15] = {0};
2493 int nFaninMax, i, k;
2494 // calculate relative gate delays
2495 nFaninMax = Abc_NtkGetFaninMax( pNtk );
2496 assert( nFaninMax > 1 && nFaninMax < 15 );
2497 for ( i = 0; i <= nFaninMax; i++ )
2498 Delays[i] = GateDelays[i]/GateDelays[nFaninMax];
2499 // set max CI delay
2500 Abc_NtkForEachCi( pNtk, pObj, i )
2501 pObj->dTemp = 0.0;
2502 // compute delays for each node
2503 vNodes = Abc_NtkDfs( pNtk, 1 );
2504 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
2505 {
2506 pObj->dTemp = 0.0;
2507 Abc_ObjForEachFanin( pObj, pFanin, k )
2508 pObj->dTemp = Abc_MaxFloat( pObj->dTemp, pFanin->dTemp );
2509 pObj->dTemp += Delays[Abc_ObjFaninNum(pObj)];
2510 }
2511 Vec_PtrFree( vNodes );
2512 DelayMax = 0.0;
2513 // find max CO delay
2514 Abc_NtkForEachCo( pNtk, pObj, i )
2515 DelayMax = Abc_MaxFloat( DelayMax, Abc_ObjFanin0(pObj)->dTemp );
2516 return DelayMax;
2517 }
2518
2519
2520 /**Function*************************************************************
2521
2522 Synopsis []
2523
2524 Description []
2525
2526 SideEffects []
2527
2528 SeeAlso []
2529
2530 ***********************************************************************/
Abc_NodeSopToCubes(Abc_Obj_t * pNodeOld,Abc_Ntk_t * pNtkNew,int fXor)2531 void Abc_NodeSopToCubes( Abc_Obj_t * pNodeOld, Abc_Ntk_t * pNtkNew, int fXor )
2532 {
2533 Abc_Obj_t * pNodeOr, * pNodeNew, * pFanin;
2534 char * pCube, * pSop = (char *)pNodeOld->pData;
2535 int v, Value, nVars = Abc_ObjFaninNum(pNodeOld), nFanins;
2536 // create the root node
2537 if ( Abc_SopGetCubeNum(pSop) < 2 )
2538 {
2539 pNodeNew = Abc_NtkDupObj( pNtkNew, pNodeOld, 0 );
2540 Abc_ObjForEachFanin( pNodeOld, pFanin, v )
2541 Abc_ObjAddFanin( pNodeNew, pFanin->pCopy );
2542 assert( pNodeOld->pCopy == pNodeNew );
2543 return;
2544 }
2545 // add the OR gate
2546 pNodeOr = Abc_NtkCreateNode( pNtkNew );
2547 if ( fXor )
2548 pNodeOr->pData = Abc_SopCreateXorSpecial( (Mem_Flex_t *)pNtkNew->pManFunc, Abc_SopGetCubeNum(pSop) );
2549 else
2550 pNodeOr->pData = Abc_SopCreateOr( (Mem_Flex_t *)pNtkNew->pManFunc, Abc_SopGetCubeNum(pSop), NULL );
2551 // check the logic function of the node
2552 Abc_SopForEachCube( pSop, nVars, pCube )
2553 {
2554 nFanins = 0;
2555 Abc_CubeForEachVar( pCube, Value, v )
2556 if ( Value == '0' || Value == '1' )
2557 nFanins++;
2558 if ( nFanins == 0 ) // const1 cube in ESOP
2559 {
2560 pNodeNew = Abc_NtkCreateNodeConst1( pNtkNew );
2561 Abc_ObjAddFanin( pNodeOr, pNodeNew );
2562 continue;
2563 }
2564 assert( nFanins > 0 );
2565 // create node
2566 pNodeNew = Abc_NtkCreateNode( pNtkNew );
2567 pNodeNew->pData = Abc_SopCreateAnd( (Mem_Flex_t *)pNtkNew->pManFunc, nFanins, NULL );
2568 nFanins = 0;
2569 Abc_CubeForEachVar( pCube, Value, v )
2570 {
2571 if ( Value != '0' && Value != '1' )
2572 continue;
2573 Abc_ObjAddFanin( pNodeNew, Abc_ObjFanin(pNodeOld, v)->pCopy );
2574 if ( Value == '0' )
2575 Abc_SopComplementVar( (char *)pNodeNew->pData, nFanins );
2576 nFanins++;
2577 }
2578 Abc_ObjAddFanin( pNodeOr, pNodeNew );
2579 }
2580 // check the complement
2581 if ( Abc_SopIsComplement(pSop) )
2582 Abc_SopComplement( (char *)pNodeOr->pData );
2583 // mark the old node with the new one
2584 assert( pNodeOld->pCopy == NULL );
2585 pNodeOld->pCopy = pNodeOr;
2586 }
Abc_NtkSopToCubes(Abc_Ntk_t * pNtk,int fXor)2587 Abc_Ntk_t * Abc_NtkSopToCubes( Abc_Ntk_t * pNtk, int fXor )
2588 {
2589 Abc_Ntk_t * pNtkNew;
2590 Abc_Obj_t * pNode;
2591 Vec_Ptr_t * vNodes;
2592 int i;
2593 assert( Abc_NtkIsSopLogic(pNtk) );
2594 Abc_NtkCleanCopy( pNtk );
2595 pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_SOP );
2596 // perform conversion in the topological order
2597 vNodes = Abc_NtkDfs( pNtk, 0 );
2598 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
2599 Abc_NodeSopToCubes( pNode, pNtkNew, fXor );
2600 Vec_PtrFree( vNodes );
2601 // make sure everything is okay
2602 Abc_NtkFinalize( pNtk, pNtkNew );
2603 if ( !Abc_NtkCheck( pNtkNew ) )
2604 {
2605 printf( "Abc_NtkSopToCubes: The network check has failed.\n" );
2606 Abc_NtkDelete( pNtkNew );
2607 return NULL;
2608 }
2609 return pNtkNew;
2610 }
2611
2612 /**Function*************************************************************
2613
2614 Synopsis [Creates precomputed reverse topological order for each node.]
2615
2616 Description []
2617
2618 SideEffects []
2619
2620 SeeAlso []
2621
2622 ***********************************************************************/
Abc_NtkTopoHasBeg(Abc_Obj_t * p)2623 static inline int Abc_NtkTopoHasBeg( Abc_Obj_t * p ) { return Vec_IntEntry(p->pNtk->vTopo, 2*Abc_ObjId(p) ); }
Abc_NtkTopoHasEnd(Abc_Obj_t * p)2624 static inline int Abc_NtkTopoHasEnd( Abc_Obj_t * p ) { return Vec_IntEntry(p->pNtk->vTopo, 2*Abc_ObjId(p)+1); }
2625
Abc_NtkTopoSetBeg(Abc_Obj_t * p)2626 static inline void Abc_NtkTopoSetBeg( Abc_Obj_t * p ) { Vec_IntWriteEntry(p->pNtk->vTopo, 2*Abc_ObjId(p) , Vec_IntSize(p->pNtk->vTopo)); }
Abc_NtkTopoSetEnd(Abc_Obj_t * p)2627 static inline void Abc_NtkTopoSetEnd( Abc_Obj_t * p ) { Vec_IntWriteEntry(p->pNtk->vTopo, 2*Abc_ObjId(p)+1, Vec_IntSize(p->pNtk->vTopo)); }
2628
Abc_NtkReverseTopoOrder_rec(Abc_Obj_t * pObj,int fThisIsPivot)2629 void Abc_NtkReverseTopoOrder_rec( Abc_Obj_t * pObj, int fThisIsPivot )
2630 {
2631 Abc_Obj_t * pNext, * pPivot = NULL;
2632 int i;
2633 if ( Abc_NodeIsTravIdCurrent( pObj ) )
2634 return;
2635 Abc_NodeSetTravIdCurrent( pObj );
2636 if ( Abc_ObjIsPo(pObj) )
2637 {
2638 Vec_IntPush( pObj->pNtk->vTopo, Abc_ObjId(pObj) );
2639 return;
2640 }
2641 assert( Abc_ObjIsNode(pObj) );
2642 // mark begining
2643 if ( fThisIsPivot )
2644 Abc_NtkTopoSetBeg( pObj );
2645 // find fanout without topo
2646 Abc_ObjForEachFanout( pObj, pNext, i )
2647 if ( !Abc_NtkTopoHasBeg(pNext) )
2648 {
2649 assert( !Abc_NtkTopoHasEnd(pNext) );
2650 Abc_NtkReverseTopoOrder_rec( pNext, 1 );
2651 pPivot = pNext;
2652 break;
2653 }
2654 Abc_ObjForEachFanout( pObj, pNext, i )
2655 if ( pNext != pPivot )
2656 Abc_NtkReverseTopoOrder_rec( pNext, 0 );
2657 // mark end
2658 if ( fThisIsPivot )
2659 Abc_NtkTopoSetEnd( pObj );
2660 // save current node
2661 Vec_IntPush( pObj->pNtk->vTopo, Abc_ObjId(pObj) );
2662 }
Abc_NtkReverseTopoOrder(Abc_Ntk_t * p)2663 void Abc_NtkReverseTopoOrder( Abc_Ntk_t * p )
2664 {
2665 Abc_Obj_t * pObj;
2666 int i;
2667 assert( p->vTopo == NULL );
2668 p->vTopo = Vec_IntAlloc( 10 * Abc_NtkObjNumMax(p) );
2669 Vec_IntFill( p->vTopo, 2 * Abc_NtkObjNumMax(p), 0 );
2670 Abc_NtkForEachNode( p, pObj, i )
2671 {
2672 if ( Abc_NtkTopoHasBeg(pObj) )
2673 continue;
2674 Abc_NtkIncrementTravId( p );
2675 Abc_NtkReverseTopoOrder_rec( pObj, 1 );
2676 }
2677 printf( "Nodes = %d. Size = %d. Ratio = %f.\n",
2678 Abc_NtkNodeNum(p), Vec_IntSize(p->vTopo), 1.0*Vec_IntSize(p->vTopo)/Abc_NtkNodeNum(p) );
2679 }
2680
Abc_NtkReverse_rec(Abc_Obj_t * pObj,Vec_Int_t * vVisited)2681 void Abc_NtkReverse_rec( Abc_Obj_t * pObj, Vec_Int_t * vVisited )
2682 {
2683 Abc_Obj_t * pNext;
2684 int i;
2685 if ( Abc_NodeIsTravIdCurrent( pObj ) )
2686 return;
2687 Abc_NodeSetTravIdCurrent( pObj );
2688 Abc_ObjForEachFanout( pObj, pNext, i )
2689 Abc_NtkReverse_rec( pNext, vVisited );
2690 Vec_IntPush( vVisited, Abc_ObjId(pObj) );
2691 }
Abc_NtkReverseTopoOrderTest(Abc_Ntk_t * p)2692 void Abc_NtkReverseTopoOrderTest( Abc_Ntk_t * p )
2693 {
2694 Vec_Int_t * vVisited;
2695 Abc_Obj_t * pObj;
2696 int i;//, k, iBeg, iEnd;
2697 abctime clk = Abc_Clock();
2698 Abc_NtkReverseTopoOrder( p );
2699 /*
2700 printf( "Reverse topological order for nodes:\n" );
2701 Abc_NtkForEachNode( p, pObj, i )
2702 {
2703 iBeg = Abc_NtkTopoHasBeg( pObj );
2704 iEnd = Abc_NtkTopoHasEnd( pObj );
2705 printf( "Node %4d : ", Abc_ObjId(pObj) );
2706 for ( k = iEnd - 1; k >= iBeg; k-- )
2707 printf( "%d ", Vec_IntEntry(p->vTopo, k) );
2708 printf( "\n" );
2709 }
2710 */
2711 Vec_IntFreeP( &p->vTopo );
2712 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
2713 // compute regular fanout orders
2714 clk = Abc_Clock();
2715 vVisited = Vec_IntAlloc( 1000 );
2716 Abc_NtkForEachNode( p, pObj, i )
2717 {
2718 Vec_IntClear( vVisited );
2719 Abc_NtkIncrementTravId( p );
2720 Abc_NtkReverse_rec( pObj, vVisited );
2721 }
2722 Vec_IntFree( vVisited );
2723 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
2724 }
2725
2726 /**Function*************************************************************
2727
2728 Synopsis [Converts multi-output PLA into an AIG with logic sharing.]
2729
2730 Description [The first argument is an array of char*-strings representing
2731 individual output of a multi-output PLA. The number of inputs (nInputs)
2732 and the number of outputs (nOutputs) are the second and third arguments.
2733 This procedure returns the AIG manager with the given number of inputs
2734 and outputs representing the PLA as a logic network with sharing.
2735
2736 For example, if the original PLA is
2737 1000 10
2738 0110 01
2739 0011 01
2740 the individual PLA for each the two outputs should be
2741 1000 1
2742 and
2743 0110 1
2744 0011 1
2745
2746 Reprsentation in terms of two char*-strings will be:
2747 char * pPlas[2] = { "1000 1\n", "0110 1\n0011 1\n" };
2748 The call to the procedure may look as follows:
2749 Abc_Ntk_t * pNtkAig = Abc_NtkFromPla( pPlas, 4, 2 );]
2750
2751 SideEffects []
2752
2753 SeeAlso []
2754
2755 ***********************************************************************/
Abc_NtkFromPla(char ** pPlas,int nInputs,int nOutputs)2756 Abc_Ntk_t * Abc_NtkFromPla( char ** pPlas, int nInputs, int nOutputs )
2757 {
2758 Fxu_Data_t Params, * p = &Params;
2759 Abc_Ntk_t * pNtkSop, * pNtkAig;
2760 Abc_Obj_t * pNode, * pFanin;
2761 int i, k;
2762 // allocate logic network with SOP local functions
2763 pNtkSop = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_SOP, 1 );
2764 pNtkSop->pName = Extra_FileNameGeneric("pla");
2765 // create primary inputs/outputs
2766 for ( i = 0; i < nInputs; i++ )
2767 Abc_NtkCreatePi( pNtkSop );
2768 for ( i = 0; i < nOutputs; i++ )
2769 Abc_NtkCreatePo( pNtkSop );
2770 Abc_NtkAddDummyPiNames( pNtkSop );
2771 Abc_NtkAddDummyPoNames( pNtkSop );
2772 // create internal nodes
2773 for ( i = 0; i < nOutputs; i++ )
2774 {
2775 pNode = Abc_NtkCreateNode( pNtkSop );
2776 Abc_NtkForEachPi( pNtkSop, pFanin, k )
2777 Abc_ObjAddFanin( pNode, pFanin );
2778 pNode->pData = Abc_SopRegister( (Mem_Flex_t *)pNtkSop->pManFunc, pPlas[i] );
2779 Abc_ObjAddFanin( Abc_NtkPo(pNtkSop, i), pNode );
2780 // check that the number of inputs is the same
2781 assert( Abc_SopGetVarNum((char*)pNode->pData) == nInputs );
2782 }
2783 if ( !Abc_NtkCheck( pNtkSop ) )
2784 fprintf( stdout, "Abc_NtkFromPla(): Network check has failed.\n" );
2785 // perform fast_extract
2786 Abc_NtkSetDefaultFxParams( p );
2787 Abc_NtkFastExtract( pNtkSop, p );
2788 Abc_NtkFxuFreeInfo( p );
2789 // convert to an AIG
2790 pNtkAig = Abc_NtkStrash( pNtkSop, 0, 1, 0 );
2791 Abc_NtkDelete( pNtkSop );
2792 return pNtkAig;
2793 }
Abc_NtkFromPlaTest()2794 void Abc_NtkFromPlaTest()
2795 {
2796 char * pPlas[2] = { "1000 1\n", "0110 1\n0011 1\n" };
2797 Abc_Ntk_t * pNtkAig = Abc_NtkFromPla( pPlas, 4, 2 );
2798 Io_WriteBlifLogic( pNtkAig, "temp.blif", 0 );
2799 Abc_NtkDelete( pNtkAig );
2800 }
2801
2802 /**Function*************************************************************
2803
2804 Synopsis [Checks if the logic network is in the topological order.]
2805
2806 Description []
2807
2808 SideEffects []
2809
2810 SeeAlso []
2811
2812 ***********************************************************************/
Abc_NtkSplitSop(Abc_Ntk_t * pNtk,int nCubesMax,int fVerbose)2813 Abc_Ntk_t * Abc_NtkSplitSop( Abc_Ntk_t * pNtk, int nCubesMax, int fVerbose )
2814 {
2815 Vec_Ptr_t * vNodes;
2816 Abc_Ntk_t * pNtkNew;
2817 Abc_Obj_t * pObj, * pFanin, * pObjNew, * pObjNewRoot;
2818 int i, k, j, nCubes, nCubesThis, nSplits;
2819 char * pSopStr, * pSopStr2, * pTempSop, Symb;
2820 if ( pNtk == NULL )
2821 return NULL;
2822 assert( !Abc_NtkIsStrash(pNtk) && !Abc_NtkIsNetlist(pNtk) );
2823 // start the network
2824 pNtkNew = Abc_NtkStartFrom( pNtk, pNtk->ntkType, pNtk->ntkFunc );
2825 // copy the internal nodes
2826 vNodes = Abc_NtkDfs( pNtk, 0 );
2827 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
2828 {
2829 assert( Abc_ObjIsNode(pObj) );
2830 pObjNewRoot = Abc_NtkDupObj( pNtkNew, pObj, 0 );
2831 nCubes = Abc_SopGetCubeNum( (char *)pObj->pData );
2832 if ( nCubes <= nCubesMax )
2833 {
2834 Abc_ObjForEachFanin( pObj, pFanin, k )
2835 Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy );
2836 continue;
2837 }
2838 nSplits = (nCubes / nCubesMax) + (int)(nCubes % nCubesMax > 0);
2839 pSopStr = (char *)pObjNewRoot->pData;
2840 pObjNewRoot->pData = Abc_SopCreateOr((Mem_Flex_t *)pNtkNew->pManFunc, nSplits, NULL);
2841 if ( Abc_SopIsComplement(pSopStr) )
2842 {
2843 Abc_SopComplement( pSopStr );
2844 Abc_SopComplement( (char *)pObjNewRoot->pData );
2845 }
2846 pTempSop = (char *)pObj->pData; pObj->pData = (char *)"?";
2847 for ( j = 0; j < nSplits; j++ )
2848 {
2849 // clone the node
2850 pObjNew = Abc_NtkDupObj( pNtkNew, pObj, 0 );
2851 Abc_ObjAddFanin( pObjNewRoot, pObjNew );
2852 // get its cubes
2853 Abc_ObjForEachFanin( pObj, pFanin, k )
2854 Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy );
2855 // create SOP for this node
2856 nCubesThis = (j < nCubes / nCubesMax) ? nCubesMax : nCubes % nCubesMax;
2857 pSopStr2 = pSopStr + (Abc_ObjFaninNum(pObj) + 3) * nCubesThis;
2858 Symb = *pSopStr2; *pSopStr2 = 0;
2859 pObjNew->pData = Abc_SopRegister( (Mem_Flex_t *)pNtkNew->pManFunc, pSopStr );
2860 *pSopStr2 = Symb;
2861 pSopStr = pSopStr2;
2862 }
2863 // update
2864 pObj->pData = pTempSop;
2865 pObj->pCopy = pObjNewRoot;
2866 }
2867 Vec_PtrFree( vNodes );
2868 Abc_NtkFinalize( pNtk, pNtkNew );
2869 // check correctness
2870 if ( !Abc_NtkCheck( pNtkNew ) )
2871 fprintf( stdout, "Abc_NtkDup(): Network check has failed.\n" );
2872 pNtk->pCopy = pNtkNew;
2873 return pNtkNew;
2874 }
2875
2876 /**Function*************************************************************
2877
2878 Synopsis [Checks if the logic network is in the topological order.]
2879
2880 Description []
2881
2882 SideEffects []
2883
2884 SeeAlso []
2885
2886 ***********************************************************************/
Abc_NtkIsTopo(Abc_Ntk_t * pNtk)2887 int Abc_NtkIsTopo( Abc_Ntk_t * pNtk )
2888 {
2889 Abc_Obj_t * pObj, * pFanin;
2890 int i, k, Counter = 0;
2891 Abc_NtkIncrementTravId( pNtk );
2892 Abc_NtkForEachCi( pNtk, pObj, i )
2893 Abc_NodeSetTravIdCurrent(pObj);
2894 Abc_NtkForEachNode( pNtk, pObj, i )
2895 {
2896 // check if fanins are in the topo order
2897 Abc_ObjForEachFanin( pObj, pFanin, k )
2898 if ( !Abc_NodeIsTravIdCurrent(pFanin) )
2899 break;
2900 if ( k != Abc_ObjFaninNum(pObj) )
2901 {
2902 if ( Counter++ == 0 )
2903 printf( "Node %d is out of topo order.\n", Abc_ObjId(pObj) );
2904 }
2905 Abc_NodeSetTravIdCurrent(pObj);
2906 }
2907 if ( Counter )
2908 printf( "Topological order does not hold for %d internal nodes.\n", Counter );
2909 return (int)(Counter == 0);
2910 }
2911
2912 /**Function*************************************************************
2913
2914 Synopsis [Transfers phase information to the new network.]
2915
2916 Description []
2917
2918 SideEffects []
2919
2920 SeeAlso []
2921
2922 ***********************************************************************/
Abc_NtkTransferPhases(Abc_Ntk_t * pNtkNew,Abc_Ntk_t * pNtk)2923 void Abc_NtkTransferPhases( Abc_Ntk_t * pNtkNew, Abc_Ntk_t * pNtk )
2924 {
2925 Abc_Obj_t * pObj;
2926 int i;
2927 assert( pNtk->vPhases != NULL );
2928 assert( Vec_IntSize(pNtk->vPhases) == Abc_NtkObjNumMax(pNtk) );
2929 assert( pNtkNew->vPhases == NULL );
2930 pNtkNew->vPhases = Vec_IntStart( Abc_NtkObjNumMax(pNtkNew) );
2931 Abc_NtkForEachObj( pNtk, pObj, i )
2932 if ( pObj->pCopy && !Abc_ObjIsNone( (Abc_Obj_t *)pObj->pCopy ) )
2933 Vec_IntWriteEntry( pNtkNew->vPhases, Abc_ObjId( (Abc_Obj_t *)pObj->pCopy ), Vec_IntEntry(pNtk->vPhases, i) );
2934 }
2935
2936 /**Function*************************************************************
2937
2938 Synopsis [Starts a new network using existing network as a model.]
2939
2940 Description []
2941
2942 SideEffects []
2943
2944 SeeAlso []
2945
2946 ***********************************************************************/
Abc_NtkDeriveWithOnePo(Abc_Ntk_t * pNtk,Vec_Int_t * vNodeIds,Vec_Int_t * vNodeValues)2947 Abc_Ntk_t * Abc_NtkDeriveWithOnePo( Abc_Ntk_t * pNtk, Vec_Int_t * vNodeIds, Vec_Int_t * vNodeValues )
2948 {
2949 int fCopyNames = 1;
2950 Abc_Ntk_t * pNtkNew;
2951 Abc_Obj_t * pObj, * pFanin, * pObjNew, * pOutputNew;
2952 Vec_Ptr_t * vFanins = Vec_PtrAlloc( 100 );
2953 int i, k, Id, Value;
2954 // start the network
2955 pNtkNew = Abc_NtkAlloc( pNtk->ntkType, pNtk->ntkFunc, 1 );
2956 // duplicate the name and the spec
2957 pNtkNew->pName = Extra_UtilStrsav(pNtk->pName);
2958 pNtkNew->pSpec = Extra_UtilStrsav(pNtk->pSpec);
2959 // clean the node copy fields
2960 Abc_NtkCleanCopy( pNtk );
2961 // map the constant nodes
2962 if ( Abc_NtkIsStrash(pNtk) && Abc_NtkIsStrash(pNtkNew) )
2963 Abc_AigConst1(pNtk)->pCopy = Abc_AigConst1(pNtkNew);
2964 // clone CIs/CIs/boxes
2965 Abc_NtkForEachPi( pNtk, pObj, i )
2966 Abc_NtkDupObj( pNtkNew, pObj, fCopyNames );
2967 //Abc_NtkForEachPo( pNtk, pObj, i )
2968 // Abc_NtkDupObj( pNtkNew, pObj, fCopyNames );
2969 // create one PO
2970 pObjNew = Abc_NtkCreateObj( pNtkNew, ABC_OBJ_PO );
2971 Abc_ObjAssignName( pObjNew, "monitor", NULL );
2972 // create boxes
2973 Abc_NtkForEachBox( pNtk, pObj, i )
2974 Abc_NtkDupBox( pNtkNew, pObj, fCopyNames );
2975
2976 // duplicate nodes (CIs/COs/latches are already duplicated)
2977 Abc_NtkForEachObj( pNtk, pObj, i )
2978 if ( pObj->pCopy == NULL && !Abc_ObjIsPo(pObj) )
2979 Abc_NtkDupObj(pNtkNew, pObj, 0);
2980 // reconnect all objects except boxes (they are already connected) and POs (they will be connected later)
2981 Abc_NtkForEachObj( pNtk, pObj, i )
2982 if ( !Abc_ObjIsPo(pObj) && !Abc_ObjIsBox(pObj) && !Abc_ObjIsBo(pObj) )
2983 Abc_ObjForEachFanin( pObj, pFanin, k )
2984 Abc_ObjAddFanin( pObj->pCopy, pFanin->pCopy );
2985
2986 // AND nodes (with interters if needed)
2987 pOutputNew = NULL;
2988 Vec_IntForEachEntryTwo( vNodeIds, vNodeValues, Id, Value, i )
2989 {
2990 pObjNew = Abc_NtkObj( pNtk, Id )->pCopy;
2991 if ( Value == 0 ) // negative polarity - add inverter
2992 pObjNew = Abc_NtkCreateNodeInv( pNtkNew, pObjNew );
2993 if ( pOutputNew == NULL )
2994 pOutputNew = pObjNew;
2995 else
2996 {
2997 Vec_PtrFillTwo( vFanins, 2, pOutputNew, pObjNew );
2998 pOutputNew = Abc_NtkCreateNodeAnd( pNtkNew, vFanins );
2999 }
3000 }
3001 Vec_PtrFree( vFanins );
3002 // create the only POs, which is the AND of the corresponding nodes
3003 Abc_ObjAddFanin( Abc_NtkPo(pNtkNew, 0), pOutputNew );
3004
3005 // check that the CI/CO/latches are copied correctly
3006 assert( Abc_NtkPoNum(pNtkNew) == 1 );
3007 assert( Abc_NtkCiNum(pNtkNew) == Abc_NtkCiNum(pNtk) );
3008 assert( Abc_NtkLatchNum(pNtkNew) == Abc_NtkLatchNum(pNtk) );
3009 return pNtkNew;
3010 }
3011
3012 /**Function*************************************************************
3013
3014 Synopsis [Derives the AIG representing a property.]
3015
3016 Description [Given is a sequential logic network (Abc_Ntk_t) and
3017 an array of nodes (vector of object IDs) and their values (vector of 0s or 1s).
3018 This procedure creates a sequential AIG (Abc_Ntk_t), which can be given to a
3019 sequential model checker (in particular "pdr") to prove that the given
3020 combination of values never appears at the intenal nodes of the network,
3021 or produce a counter-example showing that it can appear.]
3022
3023 SideEffects []
3024
3025 SeeAlso []
3026
3027 ***********************************************************************/
Abc_NtkCreatePropertyMonitor(Abc_Ntk_t * p,Vec_Int_t * vNodeIds,Vec_Int_t * vNodeValues)3028 Abc_Ntk_t * Abc_NtkCreatePropertyMonitor( Abc_Ntk_t * p, Vec_Int_t * vNodeIds, Vec_Int_t * vNodeValues )
3029 {
3030 Abc_Ntk_t * pMonitor, * pStrashed, * pResult;
3031 // sequential cleanup parameters
3032 int fLatchConst = 1;
3033 int fLatchEqual = 1;
3034 int fSaveNames = 1;
3035 int fUseMvSweep = 0;
3036 int nFramesSymb = 1;
3037 int nFramesSatur = 512;
3038 int fVerbose = 0;
3039 int fVeryVerbose = 0;
3040 // expecting sequential logic network
3041 assert( Abc_NtkIsLogic(p) );
3042 assert( Abc_NtkLatchNum(p) > 0 );
3043 assert( Vec_IntSize(vNodeIds) > 0 );
3044 assert( Vec_IntSize(vNodeIds) == Vec_IntSize(vNodeValues) );
3045 // derive ABC network whose only output is 1 iff the given nodes have the given values
3046 pMonitor = Abc_NtkDeriveWithOnePo( p, vNodeIds, vNodeValues );
3047 // perform structural hashing
3048 pStrashed = Abc_NtkStrash( pMonitor, 0, 1, 0 );
3049 Abc_NtkDelete( pMonitor );
3050 // it is a good idea to run sequential cleanup before giving the network to PDR
3051 pResult = Abc_NtkDarLatchSweep( pStrashed, fLatchConst, fLatchEqual, fSaveNames, fUseMvSweep, nFramesSymb, nFramesSatur, fVerbose, fVeryVerbose );
3052 Abc_NtkDelete( pStrashed );
3053 return pResult;
3054 }
3055
3056 /**Function*************************************************************
3057
3058 Synopsis [Testbench.]
3059
3060 Description []
3061
3062 SideEffects []
3063
3064 SeeAlso []
3065
3066 ***********************************************************************/
Abc_NtkCreatePropertyMonitorTest(Abc_Ntk_t * p)3067 Abc_Ntk_t * Abc_NtkCreatePropertyMonitorTest( Abc_Ntk_t * p )
3068 {
3069 Abc_Ntk_t * pNtk;
3070 Vec_Int_t * vNodeIds = Vec_IntAlloc( 100 );
3071 Vec_Int_t * vNodeValues = Vec_IntAlloc( 100 );
3072
3073 // this test will only work for the network, which has nodes with internal IDs such as these
3074 Vec_IntPush( vNodeIds, 90 );
3075 Vec_IntPush( vNodeIds, 80 );
3076 Vec_IntPush( vNodeIds, 100 );
3077
3078 Vec_IntPush( vNodeValues, 1 );
3079 Vec_IntPush( vNodeValues, 0 );
3080 Vec_IntPush( vNodeValues, 1 );
3081
3082 pNtk = Abc_NtkCreatePropertyMonitor( p, vNodeIds, vNodeValues );
3083
3084 Vec_IntFree( vNodeIds );
3085 Vec_IntFree( vNodeValues );
3086
3087 return pNtk;
3088 }
3089
3090 /**Function*************************************************************
3091
3092 Synopsis []
3093
3094 Description []
3095
3096 SideEffects []
3097
3098 SeeAlso []
3099
3100 ***********************************************************************/
Abc_GateToType(Abc_Obj_t * pObj)3101 int Abc_GateToType( Abc_Obj_t * pObj )
3102 {
3103 char * pGateName = Mio_GateReadName((Mio_Gate_t *)pObj->pData);
3104 if ( !strncmp(pGateName, "buf", 3) ) return ABC_OPER_BIT_BUF;
3105 if ( !strncmp(pGateName, "inv", 3) ) return ABC_OPER_BIT_INV;
3106 if ( !strncmp(pGateName, "and", 3) ) return ABC_OPER_BIT_AND;
3107 if ( !strncmp(pGateName, "nand", 4) ) return ABC_OPER_BIT_NAND;
3108 if ( !strncmp(pGateName, "or", 2) ) return ABC_OPER_BIT_OR;
3109 if ( !strncmp(pGateName, "nor", 3) ) return ABC_OPER_BIT_NOR;
3110 if ( !strncmp(pGateName, "xor", 3) ) return ABC_OPER_BIT_XOR;
3111 if ( !strncmp(pGateName, "xnor", 4) ) return ABC_OPER_BIT_NXOR;
3112 if ( !strncmp(pGateName, "zero", 4) ) return ABC_OPER_CONST_F;
3113 if ( !strncmp(pGateName, "one", 3) ) return ABC_OPER_CONST_T;
3114 assert( 0 );
3115 return -1;
3116 }
Abc_SopSynthesize(Vec_Ptr_t * vSops)3117 Vec_Wec_t * Abc_SopSynthesize( Vec_Ptr_t * vSops )
3118 {
3119 Vec_Wec_t * vRes = NULL;
3120 Abc_Ntk_t * pNtk = Abc_NtkCreateFromSops( "top", vSops );
3121 Abc_Ntk_t * pNtkNew;
3122 Abc_Obj_t * pObj, * pFanin;
3123 int i, k, iNode = 0;
3124 Abc_FrameReplaceCurrentNetwork( Abc_FrameReadGlobalFrame(), pNtk );
3125 Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "fx; strash; balance; dc2; map -a" );
3126 pNtkNew = Abc_FrameReadNtk( Abc_FrameReadGlobalFrame() );
3127 vRes = Vec_WecStart( Abc_NtkPiNum(pNtkNew) + Abc_NtkNodeNum(pNtkNew) + Abc_NtkPoNum(pNtkNew) );
3128 Abc_NtkForEachPi( pNtkNew, pObj, i )
3129 pObj->iTemp = iNode++;
3130 Abc_NtkForEachNode( pNtkNew, pObj, i )
3131 {
3132 Vec_Int_t * vNode = Vec_WecEntry(vRes, iNode);
3133 Vec_IntPush( vNode, Abc_GateToType(pObj) );
3134 Vec_IntPush( vNode, iNode );
3135 Abc_ObjForEachFanin( pObj, pFanin, k )
3136 Vec_IntPush( vNode, pFanin->iTemp );
3137 pObj->iTemp = iNode++;
3138 }
3139 Abc_NtkForEachPo( pNtkNew, pObj, i )
3140 Vec_IntPushTwo( Vec_WecEntry(vRes, iNode++), ABC_OPER_BIT_BUF, Abc_ObjFanin0(pObj)->iTemp );
3141 assert( Vec_WecSize(vRes) == iNode );
3142 return vRes;
3143 }
Abc_GiaSynthesize(Vec_Ptr_t * vGias,Gia_Man_t * pMulti)3144 Vec_Wec_t * Abc_GiaSynthesize( Vec_Ptr_t * vGias, Gia_Man_t * pMulti )
3145 {
3146 Vec_Wec_t * vRes = NULL;
3147 Abc_Ntk_t * pNtk = Abc_NtkCreateFromGias( "top", vGias, pMulti );
3148 Abc_Ntk_t * pNtkNew;
3149 Abc_Obj_t * pObj, * pFanin;
3150 int i, k, iNode = 0;
3151 Abc_FrameReplaceCurrentNetwork( Abc_FrameReadGlobalFrame(), pNtk );
3152 Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "compress2rs; dch; map -a; strash; compress2rs; dch; map -a; strash; compress2rs; dch; map -a" );
3153 pNtkNew = Abc_FrameReadNtk( Abc_FrameReadGlobalFrame() );
3154 vRes = Vec_WecStart( Abc_NtkPiNum(pNtkNew) + Abc_NtkNodeNum(pNtkNew) + Abc_NtkPoNum(pNtkNew) );
3155 Abc_NtkForEachPi( pNtkNew, pObj, i )
3156 pObj->iTemp = iNode++;
3157 Abc_NtkForEachNode( pNtkNew, pObj, i )
3158 {
3159 Vec_Int_t * vNode = Vec_WecEntry(vRes, iNode);
3160 Vec_IntPush( vNode, Abc_GateToType(pObj) );
3161 Vec_IntPush( vNode, iNode );
3162 Abc_ObjForEachFanin( pObj, pFanin, k )
3163 Vec_IntPush( vNode, pFanin->iTemp );
3164 pObj->iTemp = iNode++;
3165 }
3166 Abc_NtkForEachPo( pNtkNew, pObj, i )
3167 Vec_IntPushTwo( Vec_WecEntry(vRes, iNode++), ABC_OPER_BIT_BUF, Abc_ObjFanin0(pObj)->iTemp );
3168 assert( Vec_WecSize(vRes) == iNode );
3169 return vRes;
3170 }
Abc_GiaSynthesizeInter(Gia_Man_t * p)3171 Gia_Man_t * Abc_GiaSynthesizeInter( Gia_Man_t * p )
3172 {
3173 Abc_Ntk_t * pNtkNew, * pNtk;
3174 Vec_Ptr_t * vGias = Vec_PtrAlloc( 1 );
3175 Vec_PtrPush( vGias, p );
3176 pNtk = Abc_NtkCreateFromGias( "top", vGias, NULL );
3177 Vec_PtrFree( vGias );
3178 Abc_FrameReplaceCurrentNetwork( Abc_FrameReadGlobalFrame(), pNtk );
3179 Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "balance; collapse; muxes; strash; dc2" );
3180 pNtkNew = Abc_FrameReadNtk( Abc_FrameReadGlobalFrame() );
3181 return Abc_NtkClpGia( pNtkNew );
3182 }
3183
3184 /**Function*************************************************************
3185
3186 Synopsis []
3187
3188 Description []
3189
3190 SideEffects []
3191
3192 SeeAlso []
3193
3194 ***********************************************************************/
Abc_NtkClpOneGia_rec(Gia_Man_t * pNew,Abc_Obj_t * pNode)3195 int Abc_NtkClpOneGia_rec( Gia_Man_t * pNew, Abc_Obj_t * pNode )
3196 {
3197 int iLit0, iLit1;
3198 if ( Abc_NodeIsTravIdCurrent(pNode) || Abc_ObjFaninNum(pNode) == 0 || Abc_ObjIsCi(pNode) )
3199 return pNode->iTemp;
3200 assert( Abc_ObjIsNode( pNode ) );
3201 Abc_NodeSetTravIdCurrent( pNode );
3202 iLit0 = Abc_NtkClpOneGia_rec( pNew, Abc_ObjFanin0(pNode) );
3203 iLit1 = Abc_NtkClpOneGia_rec( pNew, Abc_ObjFanin1(pNode) );
3204 iLit0 = Abc_LitNotCond( iLit0, Abc_ObjFaninC0(pNode) );
3205 iLit1 = Abc_LitNotCond( iLit1, Abc_ObjFaninC1(pNode) );
3206 return (pNode->iTemp = Gia_ManHashAnd(pNew, iLit0, iLit1));
3207 }
Abc_NtkStrashToGia(Abc_Ntk_t * pNtk)3208 Gia_Man_t * Abc_NtkStrashToGia( Abc_Ntk_t * pNtk )
3209 {
3210 int i, iLit;
3211 Abc_Obj_t * pNode;
3212 Gia_Man_t * pNew, * pTemp;
3213 assert( Abc_NtkIsStrash(pNtk) );
3214 Abc_NtkForEachObj( pNtk, pNode, i )
3215 pNode->iTemp = -1;
3216 // start new manager
3217 pNew = Gia_ManStart( Abc_NtkObjNum(pNtk) );
3218 pNew->pName = Abc_UtilStrsav( pNtk->pName );
3219 pNew->pSpec = Abc_UtilStrsav( pNtk->pSpec );
3220 Gia_ManHashStart( pNew );
3221 // primary inputs
3222 Abc_AigConst1(pNtk)->iTemp = 1;
3223 Abc_NtkForEachCi( pNtk, pNode, i )
3224 pNode->iTemp = Gia_ManAppendCi(pNew);
3225 // create the first cone
3226 Abc_NtkIncrementTravId( pNtk );
3227 Abc_NtkForEachCo( pNtk, pNode, i )
3228 {
3229 iLit = Abc_NtkClpOneGia_rec( pNew, Abc_ObjFanin0(pNode) );
3230 iLit = Abc_LitNotCond( iLit, Abc_ObjFaninC0(pNode) );
3231 Gia_ManAppendCo( pNew, iLit );
3232 }
3233 // perform cleanup
3234 pNew = Gia_ManCleanup( pTemp = pNew );
3235 Gia_ManStop( pTemp );
3236 return pNew;
3237 }
Abc_SopSynthesizeOne(char * pSop,int fClp)3238 Gia_Man_t * Abc_SopSynthesizeOne( char * pSop, int fClp )
3239 {
3240 Abc_Ntk_t * pNtkNew, * pNtk;
3241 Vec_Ptr_t * vSops;
3242 if ( strlen(pSop) == 3 )
3243 {
3244 Gia_Man_t * pNew = Gia_ManStart( 1 );
3245 pNew->pName = Abc_UtilStrsav( "top" );
3246 //Gia_ManAppendCi( pNew );
3247 assert( pSop[1] == '0' || pSop[1] == '1' );
3248 Gia_ManAppendCo( pNew, pSop[1] == '1' );
3249 return pNew;
3250 }
3251 vSops = Vec_PtrAlloc( 1 );
3252 Vec_PtrPush( vSops, pSop );
3253 pNtk = Abc_NtkCreateFromSops( "top", vSops );
3254 Vec_PtrFree( vSops );
3255 Abc_FrameReplaceCurrentNetwork( Abc_FrameReadGlobalFrame(), pNtk );
3256 if ( fClp )
3257 Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "clp; sop" );
3258 Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "fx; strash; balance; dc2" );
3259 pNtkNew = Abc_FrameReadNtk( Abc_FrameReadGlobalFrame() );
3260 return Abc_NtkStrashToGia( pNtkNew );
3261 }
3262
3263 ////////////////////////////////////////////////////////////////////////
3264 /// END OF FILE ///
3265 ////////////////////////////////////////////////////////////////////////
3266
3267
3268 ABC_NAMESPACE_IMPL_END
3269
3270