1 /**CFile****************************************************************
2
3 FileName [abcDfs.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Network and node package.]
8
9 Synopsis [Procedures that use depth-first search.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: abcDfs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "abc.h"
22 #include "proof/cec/cec.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30
31 ////////////////////////////////////////////////////////////////////////
32 /// FUNCTION DEFINITIONS ///
33 ////////////////////////////////////////////////////////////////////////
34
35 /**Function*************************************************************
36
37 Synopsis [Performs DFS for one node.]
38
39 Description []
40
41 SideEffects []
42
43 SeeAlso []
44
45 ***********************************************************************/
Abc_NtkDfs_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)46 void Abc_NtkDfs_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
47 {
48 Abc_Obj_t * pFanin;
49 int i;
50 assert( !Abc_ObjIsNet(pNode) );
51 // if this node is already visited, skip
52 if ( Abc_NodeIsTravIdCurrent( pNode ) )
53 return;
54 // mark the node as visited
55 Abc_NodeSetTravIdCurrent( pNode );
56 // skip the CI
57 if ( Abc_ObjIsCi(pNode) || (Abc_NtkIsStrash(pNode->pNtk) && Abc_AigNodeIsConst(pNode)) )
58 return;
59 assert( Abc_ObjIsNode( pNode ) || Abc_ObjIsBox( pNode ) );
60 // visit the transitive fanin of the node
61 Abc_ObjForEachFanin( pNode, pFanin, i )
62 {
63 // pFanin = Abc_ObjFanin( pNode, Abc_ObjFaninNum(pNode)-1-i );
64 Abc_NtkDfs_rec( Abc_ObjFanin0Ntk(pFanin), vNodes );
65 }
66 // add the node after the fanins have been added
67 Vec_PtrPush( vNodes, pNode );
68 }
69
70 /**Function*************************************************************
71
72 Synopsis [Returns the DFS ordered array of logic nodes.]
73
74 Description [Collects only the internal nodes, leaving out CIs and CO.
75 However it marks with the current TravId both CIs and COs.]
76
77 SideEffects []
78
79 SeeAlso []
80
81 ***********************************************************************/
Abc_NtkDfs(Abc_Ntk_t * pNtk,int fCollectAll)82 Vec_Ptr_t * Abc_NtkDfs( Abc_Ntk_t * pNtk, int fCollectAll )
83 {
84 Vec_Ptr_t * vNodes;
85 Abc_Obj_t * pObj;
86 int i;
87 // set the traversal ID
88 Abc_NtkIncrementTravId( pNtk );
89 // start the array of nodes
90 vNodes = Vec_PtrAlloc( 100 );
91 if ( pNtk->nBarBufs2 > 0 )
92 {
93 Abc_NtkForEachBarBuf( pNtk, pObj, i )
94 {
95 Abc_NodeSetTravIdCurrent( pObj );
96 Abc_NtkDfs_rec( Abc_ObjFanin0Ntk(Abc_ObjFanin0(pObj)), vNodes );
97 Vec_PtrPush( vNodes, pObj );
98 }
99 }
100 Abc_NtkForEachCo( pNtk, pObj, i )
101 {
102 Abc_NodeSetTravIdCurrent( pObj );
103 Abc_NtkDfs_rec( Abc_ObjFanin0Ntk(Abc_ObjFanin0(pObj)), vNodes );
104 }
105 // collect dangling nodes if asked to
106 if ( fCollectAll )
107 {
108 Abc_NtkForEachNode( pNtk, pObj, i )
109 if ( !Abc_NodeIsTravIdCurrent(pObj) )
110 Abc_NtkDfs_rec( pObj, vNodes );
111 }
112 return vNodes;
113 }
114
115 /**Function*************************************************************
116
117 Synopsis [Returns the DFS ordered array of logic nodes.]
118
119 Description [Collects only the internal nodes, leaving out CIs and CO.
120 However it marks with the current TravId both CIs and COs.]
121
122 SideEffects []
123
124 SeeAlso []
125
126 ***********************************************************************/
Abc_NtkDfs2(Abc_Ntk_t * pNtk)127 Vec_Ptr_t * Abc_NtkDfs2( Abc_Ntk_t * pNtk )
128 {
129 Vec_Ptr_t * vNodes = Vec_PtrAlloc( 100 );
130 Abc_Obj_t * pObj; int i;
131 Abc_NtkIncrementTravId( pNtk );
132 Abc_NtkForEachCo( pNtk, pObj, i )
133 {
134 Abc_NodeSetTravIdCurrent( pObj );
135 Abc_NtkDfs_rec( Abc_ObjFanin0Ntk(Abc_ObjFanin0(pObj)), vNodes );
136 }
137 return vNodes;
138 }
139
140 /**Function*************************************************************
141
142 Synopsis [Returns the DFS ordered array of logic nodes.]
143
144 Description [Collects only the internal nodes, leaving out PIs, POs and latches.]
145
146 SideEffects []
147
148 SeeAlso []
149
150 ***********************************************************************/
Abc_NtkDfsNodes(Abc_Ntk_t * pNtk,Abc_Obj_t ** ppNodes,int nNodes)151 Vec_Ptr_t * Abc_NtkDfsNodes( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppNodes, int nNodes )
152 {
153 Vec_Ptr_t * vNodes;
154 int i;
155 // set the traversal ID
156 Abc_NtkIncrementTravId( pNtk );
157 // start the array of nodes
158 vNodes = Vec_PtrAlloc( 100 );
159 // go through the PO nodes and call for each of them
160 for ( i = 0; i < nNodes; i++ )
161 {
162 if ( Abc_NtkIsStrash(pNtk) && Abc_AigNodeIsConst(ppNodes[i]) )
163 continue;
164 if ( Abc_ObjIsCo(ppNodes[i]) )
165 {
166 Abc_NodeSetTravIdCurrent(ppNodes[i]);
167 Abc_NtkDfs_rec( Abc_ObjFanin0Ntk(Abc_ObjFanin0(ppNodes[i])), vNodes );
168 }
169 else if ( Abc_ObjIsNode(ppNodes[i]) || Abc_ObjIsCi(ppNodes[i]) )
170 Abc_NtkDfs_rec( ppNodes[i], vNodes );
171 }
172 return vNodes;
173 }
174
175
176 /**Function*************************************************************
177
178 Synopsis [Performs DFS for one node.]
179
180 Description []
181
182 SideEffects []
183
184 SeeAlso []
185
186 ***********************************************************************/
Abc_NtkDfsReverse_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)187 void Abc_NtkDfsReverse_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
188 {
189 Abc_Obj_t * pFanout;
190 int i;
191 assert( !Abc_ObjIsNet(pNode) );
192 // if this node is already visited, skip
193 if ( Abc_NodeIsTravIdCurrent( pNode ) )
194 return;
195 // mark the node as visited
196 Abc_NodeSetTravIdCurrent( pNode );
197 // skip the CI
198 if ( Abc_ObjIsCo(pNode) )
199 return;
200 assert( Abc_ObjIsNode( pNode ) );
201 // visit the transitive fanin of the node
202 pNode = Abc_ObjFanout0Ntk(pNode);
203 Abc_ObjForEachFanout( pNode, pFanout, i )
204 Abc_NtkDfsReverse_rec( pFanout, vNodes );
205 // add the node after the fanins have been added
206 Vec_PtrPush( vNodes, pNode );
207 }
208
209 /**Function*************************************************************
210
211 Synopsis [Returns the reverse DFS ordered array of logic nodes.]
212
213 Description [Collects only the internal nodes, leaving out CIs/COs.
214 However it marks both CIs and COs with the current TravId.]
215
216 SideEffects []
217
218 SeeAlso []
219
220 ***********************************************************************/
Abc_NtkDfsReverse(Abc_Ntk_t * pNtk)221 Vec_Ptr_t * Abc_NtkDfsReverse( Abc_Ntk_t * pNtk )
222 {
223 Vec_Ptr_t * vNodes;
224 Abc_Obj_t * pObj, * pFanout;
225 int i, k;
226 // set the traversal ID
227 Abc_NtkIncrementTravId( pNtk );
228 // start the array of nodes
229 vNodes = Vec_PtrAlloc( 100 );
230 Abc_NtkForEachCi( pNtk, pObj, i )
231 {
232 Abc_NodeSetTravIdCurrent( pObj );
233 pObj = Abc_ObjFanout0Ntk(pObj);
234 Abc_ObjForEachFanout( pObj, pFanout, k )
235 Abc_NtkDfsReverse_rec( pFanout, vNodes );
236 }
237 // add constant nodes in the end
238 if ( !Abc_NtkIsStrash(pNtk) ) {
239 Abc_NtkForEachNode( pNtk, pObj, i )
240 if ( Abc_NodeIsConst(pObj) )
241 Vec_PtrPush( vNodes, pObj );
242 }
243 return vNodes;
244 }
245
246 /**Function*************************************************************
247
248 Synopsis [Performs DFS for one node.]
249
250 Description []
251
252 SideEffects []
253
254 SeeAlso []
255
256 ***********************************************************************/
Abc_NtkDfsReverseNodes_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)257 void Abc_NtkDfsReverseNodes_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
258 {
259 Abc_Obj_t * pFanout;
260 int i;
261 assert( !Abc_ObjIsNet(pNode) );
262 // if this node is already visited, skip
263 if ( Abc_NodeIsTravIdCurrent( pNode ) )
264 return;
265 // mark the node as visited
266 Abc_NodeSetTravIdCurrent( pNode );
267 // skip the CI
268 if ( Abc_ObjIsCo(pNode) )
269 return;
270 assert( Abc_ObjIsNode( pNode ) );
271 // visit the transitive fanin of the node
272 pNode = Abc_ObjFanout0Ntk(pNode);
273 Abc_ObjForEachFanout( pNode, pFanout, i )
274 Abc_NtkDfsReverseNodes_rec( pFanout, vNodes );
275 // add the node after the fanins have been added
276 // Vec_PtrPush( vNodes, pNode );
277 Vec_PtrFillExtra( vNodes, pNode->Level + 1, NULL );
278 pNode->pCopy = (Abc_Obj_t *)Vec_PtrEntry( vNodes, pNode->Level );
279 Vec_PtrWriteEntry( vNodes, pNode->Level, pNode );
280 }
281
282 /**Function*************************************************************
283
284 Synopsis [Returns the levelized array of TFO nodes.]
285
286 Description [Collects the levelized array of internal nodes, leaving out CIs/COs.
287 However it marks both CIs and COs with the current TravId.]
288
289 SideEffects []
290
291 SeeAlso []
292
293 ***********************************************************************/
Abc_NtkDfsReverseNodes(Abc_Ntk_t * pNtk,Abc_Obj_t ** ppNodes,int nNodes)294 Vec_Ptr_t * Abc_NtkDfsReverseNodes( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppNodes, int nNodes )
295 {
296 Vec_Ptr_t * vNodes;
297 Abc_Obj_t * pObj, * pFanout;
298 int i, k;
299 assert( Abc_NtkIsStrash(pNtk) );
300 // set the traversal ID
301 Abc_NtkIncrementTravId( pNtk );
302 // start the array of nodes
303 vNodes = Vec_PtrStart( Abc_AigLevel(pNtk) + 1 );
304 for ( i = 0; i < nNodes; i++ )
305 {
306 pObj = ppNodes[i];
307 assert( Abc_ObjIsCi(pObj) );
308 Abc_NodeSetTravIdCurrent( pObj );
309 pObj = Abc_ObjFanout0Ntk(pObj);
310 Abc_ObjForEachFanout( pObj, pFanout, k )
311 Abc_NtkDfsReverseNodes_rec( pFanout, vNodes );
312 }
313 return vNodes;
314 }
315
316 /**Function*************************************************************
317
318 Synopsis [Returns the levelized array of TFO nodes.]
319
320 Description [Collects the levelized array of internal nodes, leaving out CIs/COs.
321 However it marks both CIs and COs with the current TravId.
322 Collects only the nodes whose support does not exceed the set of given CI nodes.]
323
324 SideEffects []
325
326 SeeAlso []
327
328 ***********************************************************************/
Abc_NtkDfsReverseNodesContained(Abc_Ntk_t * pNtk,Abc_Obj_t ** ppNodes,int nNodes)329 Vec_Ptr_t * Abc_NtkDfsReverseNodesContained( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppNodes, int nNodes )
330 {
331 Vec_Ptr_t * vNodes;
332 Abc_Obj_t * pObj, * pFanout, * pFanin;
333 int i, k, m, nLevels;
334 // set the levels
335 nLevels = Abc_NtkLevel( pNtk );
336 // set the traversal ID
337 Abc_NtkIncrementTravId( pNtk );
338 // start the array of nodes
339 vNodes = Vec_PtrStart( nLevels + 2 );
340 for ( i = 0; i < nNodes; i++ )
341 {
342 pObj = ppNodes[i];
343 assert( Abc_ObjIsCi(pObj) );
344 Abc_NodeSetTravIdCurrent( pObj );
345 // add to the array
346 assert( pObj->Level == 0 );
347 pObj->pCopy = (Abc_Obj_t *)Vec_PtrEntry( vNodes, pObj->Level );
348 Vec_PtrWriteEntry( vNodes, pObj->Level, pObj );
349 }
350 // iterate through the levels
351 for ( i = 0; i <= nLevels; i++ )
352 {
353 // iterate through the nodes on each level
354 for ( pObj = (Abc_Obj_t *)Vec_PtrEntry(vNodes, i); pObj; pObj = pObj->pCopy )
355 {
356 // iterate through the fanouts of each node
357 Abc_ObjForEachFanout( pObj, pFanout, k )
358 {
359 // skip visited nodes
360 if ( Abc_NodeIsTravIdCurrent(pFanout) )
361 continue;
362 // visit the fanins of this fanout
363 Abc_ObjForEachFanin( pFanout, pFanin, m )
364 {
365 if ( !Abc_NodeIsTravIdCurrent(pFanin) )
366 break;
367 }
368 if ( m < Abc_ObjFaninNum(pFanout) )
369 continue;
370 // all fanins are already collected
371
372 // mark the node as visited
373 Abc_NodeSetTravIdCurrent( pFanout );
374 // handle the COs
375 if ( Abc_ObjIsCo(pFanout) )
376 pFanout->Level = nLevels + 1;
377 // add to the array
378 pFanout->pCopy = (Abc_Obj_t *)Vec_PtrEntry( vNodes, pFanout->Level );
379 Vec_PtrWriteEntry( vNodes, pFanout->Level, pFanout );
380 // handle the COs
381 if ( Abc_ObjIsCo(pFanout) )
382 pFanout->Level = 0;
383 }
384 }
385 }
386 return vNodes;
387 }
388
389
390 /**Function*************************************************************
391
392 Synopsis [Performs DFS for one node.]
393
394 Description []
395
396 SideEffects []
397
398 SeeAlso []
399
400 ***********************************************************************/
Abc_NtkDfsSeq_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)401 void Abc_NtkDfsSeq_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
402 {
403 Abc_Obj_t * pFanin;
404 int i;
405 // if this node is already visited, skip
406 if ( Abc_NodeIsTravIdCurrent( pNode ) )
407 return;
408 // mark the node as visited
409 Abc_NodeSetTravIdCurrent( pNode );
410 // visit the transitive fanin of the node
411 Abc_ObjForEachFanin( pNode, pFanin, i )
412 Abc_NtkDfsSeq_rec( pFanin, vNodes );
413 // add the node after the fanins have been added
414 Vec_PtrPush( vNodes, pNode );
415 }
416
417 /**Function*************************************************************
418
419 Synopsis [Returns the array of nodes and latches reachable from POs.]
420
421 Description []
422
423 SideEffects []
424
425 SeeAlso []
426
427 ***********************************************************************/
Abc_NtkDfsSeq(Abc_Ntk_t * pNtk)428 Vec_Ptr_t * Abc_NtkDfsSeq( Abc_Ntk_t * pNtk )
429 {
430 Vec_Ptr_t * vNodes;
431 Abc_Obj_t * pObj;
432 int i;
433 assert( !Abc_NtkIsNetlist(pNtk) );
434 // set the traversal ID
435 Abc_NtkIncrementTravId( pNtk );
436 // start the array of nodes
437 vNodes = Vec_PtrAlloc( 100 );
438 Abc_NtkForEachPo( pNtk, pObj, i )
439 Abc_NtkDfsSeq_rec( pObj, vNodes );
440 // mark the PIs
441 Abc_NtkForEachPi( pNtk, pObj, i )
442 Abc_NtkDfsSeq_rec( pObj, vNodes );
443 return vNodes;
444 }
445
446
447 /**Function*************************************************************
448
449 Synopsis [Performs DFS for one node.]
450
451 Description []
452
453 SideEffects []
454
455 SeeAlso []
456
457 ***********************************************************************/
Abc_NtkDfsSeqReverse_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)458 void Abc_NtkDfsSeqReverse_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
459 {
460 Abc_Obj_t * pFanout;
461 int i;
462 // if this node is already visited, skip
463 if ( Abc_NodeIsTravIdCurrent( pNode ) )
464 return;
465 // mark the node as visited
466 Abc_NodeSetTravIdCurrent( pNode );
467 // visit the transitive fanin of the node
468 Abc_ObjForEachFanout( pNode, pFanout, i )
469 Abc_NtkDfsSeqReverse_rec( pFanout, vNodes );
470 // add the node after the fanins have been added
471 Vec_PtrPush( vNodes, pNode );
472 }
473
474 /**Function*************************************************************
475
476 Synopsis [Returns the array of nodes and latches reachable from POs.]
477
478 Description []
479
480 SideEffects []
481
482 SeeAlso []
483
484 ***********************************************************************/
Abc_NtkDfsSeqReverse(Abc_Ntk_t * pNtk)485 Vec_Ptr_t * Abc_NtkDfsSeqReverse( Abc_Ntk_t * pNtk )
486 {
487 Vec_Ptr_t * vNodes;
488 Abc_Obj_t * pObj;
489 int i;
490 assert( !Abc_NtkIsNetlist(pNtk) );
491 // set the traversal ID
492 Abc_NtkIncrementTravId( pNtk );
493 // start the array of nodes
494 vNodes = Vec_PtrAlloc( 100 );
495 Abc_NtkForEachPi( pNtk, pObj, i )
496 Abc_NtkDfsSeqReverse_rec( pObj, vNodes );
497 // mark the logic feeding into POs
498 Abc_NtkForEachPo( pNtk, pObj, i )
499 Abc_NtkDfsSeq_rec( pObj, vNodes );
500 return vNodes;
501 }
502
503
504 /**Function*************************************************************
505
506 Synopsis [Iterative version of the DFS procedure.]
507
508 Description []
509
510 SideEffects []
511
512 SeeAlso []
513
514 ***********************************************************************/
Abc_NtkDfs_iter(Vec_Ptr_t * vStack,Abc_Obj_t * pRoot,Vec_Ptr_t * vNodes)515 void Abc_NtkDfs_iter( Vec_Ptr_t * vStack, Abc_Obj_t * pRoot, Vec_Ptr_t * vNodes )
516 {
517 Abc_Obj_t * pNode, * pFanin;
518 int iFanin;
519 // if this node is already visited, skip
520 if ( Abc_NodeIsTravIdCurrent( pRoot ) )
521 return;
522 // mark the node as visited
523 Abc_NodeSetTravIdCurrent( pRoot );
524 // skip the CI
525 if ( Abc_ObjIsCi(pRoot) || (Abc_NtkIsStrash(pRoot->pNtk) && Abc_AigNodeIsConst(pRoot)) )
526 return;
527 // add the CI
528 Vec_PtrClear( vStack );
529 Vec_PtrPush( vStack, pRoot );
530 Vec_PtrPush( vStack, (void *)0 );
531 while ( Vec_PtrSize(vStack) > 0 )
532 {
533 // get the node and its fanin
534 iFanin = (int)(ABC_PTRINT_T)Vec_PtrPop(vStack);
535 pNode = (Abc_Obj_t *)Vec_PtrPop(vStack);
536 assert( !Abc_ObjIsNet(pNode) );
537 // add it to the array of nodes if we finished
538 if ( iFanin == Abc_ObjFaninNum(pNode) )
539 {
540 Vec_PtrPush( vNodes, pNode );
541 continue;
542 }
543 // explore the next fanin
544 Vec_PtrPush( vStack, pNode );
545 Vec_PtrPush( vStack, (void *)(ABC_PTRINT_T)(iFanin+1) );
546 // get the fanin
547 pFanin = Abc_ObjFanin0Ntk( Abc_ObjFanin(pNode,iFanin) );
548 // if this node is already visited, skip
549 if ( Abc_NodeIsTravIdCurrent( pFanin ) )
550 continue;
551 // mark the node as visited
552 Abc_NodeSetTravIdCurrent( pFanin );
553 // skip the CI
554 if ( Abc_ObjIsCi(pFanin) || (Abc_NtkIsStrash(pFanin->pNtk) && Abc_AigNodeIsConst(pFanin)) )
555 continue;
556 Vec_PtrPush( vStack, pFanin );
557 Vec_PtrPush( vStack, (void *)0 );
558 }
559 }
560
561 /**Function*************************************************************
562
563 Synopsis [Returns the DFS ordered array of logic nodes.]
564
565 Description [Collects only the internal nodes, leaving CIs and CO.
566 However it marks with the current TravId both CIs and COs.]
567
568 SideEffects []
569
570 SeeAlso []
571
572 ***********************************************************************/
Abc_NtkDfsIter(Abc_Ntk_t * pNtk,int fCollectAll)573 Vec_Ptr_t * Abc_NtkDfsIter( Abc_Ntk_t * pNtk, int fCollectAll )
574 {
575 Vec_Ptr_t * vNodes, * vStack;
576 Abc_Obj_t * pObj;
577 int i;
578 // set the traversal ID
579 Abc_NtkIncrementTravId( pNtk );
580 // start the array of nodes
581 vNodes = Vec_PtrAlloc( 1000 );
582 vStack = Vec_PtrAlloc( 1000 );
583 Abc_NtkForEachCo( pNtk, pObj, i )
584 {
585 Abc_NodeSetTravIdCurrent( pObj );
586 Abc_NtkDfs_iter( vStack, Abc_ObjFanin0Ntk(Abc_ObjFanin0(pObj)), vNodes );
587 }
588 // collect dangling nodes if asked to
589 if ( fCollectAll )
590 {
591 Abc_NtkForEachNode( pNtk, pObj, i )
592 if ( !Abc_NodeIsTravIdCurrent(pObj) )
593 Abc_NtkDfs_iter( vStack, pObj, vNodes );
594 }
595 Vec_PtrFree( vStack );
596 return vNodes;
597 }
598
599 /**Function*************************************************************
600
601 Synopsis [Returns the DFS ordered array of logic nodes.]
602
603 Description [Collects only the internal nodes, leaving CIs and CO.
604 However it marks with the current TravId both CIs and COs.]
605
606 SideEffects []
607
608 SeeAlso []
609
610 ***********************************************************************/
Abc_NtkDfsIterNodes(Abc_Ntk_t * pNtk,Vec_Ptr_t * vRoots)611 Vec_Ptr_t * Abc_NtkDfsIterNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots )
612 {
613 Vec_Ptr_t * vNodes, * vStack;
614 Abc_Obj_t * pObj;
615 int i;
616 Abc_NtkIncrementTravId( pNtk );
617 vNodes = Vec_PtrAlloc( 1000 );
618 vStack = Vec_PtrAlloc( 1000 );
619 Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
620 if ( !Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pObj)) )
621 Abc_NtkDfs_iter( vStack, Abc_ObjRegular(pObj), vNodes );
622 Vec_PtrFree( vStack );
623 return vNodes;
624 }
625
626
627 /**Function*************************************************************
628
629 Synopsis [Performs DFS for one node.]
630
631 Description []
632
633 SideEffects []
634
635 SeeAlso []
636
637 ***********************************************************************/
Abc_NtkDfsHie_rec(Abc_Obj_t * pObj,Vec_Ptr_t * vNodes)638 void Abc_NtkDfsHie_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vNodes )
639 {
640 Abc_Obj_t * pFanin;
641 int i;
642 // if this node is already visited, skip
643 if ( Abc_NodeIsTravIdCurrent( pObj ) )
644 return;
645 // mark the node as visited
646 Abc_NodeSetTravIdCurrent( pObj );
647 // visit the transitive fanin of the node
648 Abc_ObjForEachFanin( pObj, pFanin, i )
649 Abc_NtkDfsHie_rec( pFanin, vNodes );
650 // add the node after the fanins have been added
651 Vec_PtrPush( vNodes, pObj );
652 }
653
654 /**Function*************************************************************
655
656 Synopsis [Returns the DFS ordered array of all objects.]
657
658 Description [This procedure collects everything from POs to PIs.]
659
660 SideEffects []
661
662 SeeAlso []
663
664 ***********************************************************************/
Abc_NtkDfsHie(Abc_Ntk_t * pNtk,int fCollectAll)665 Vec_Ptr_t * Abc_NtkDfsHie( Abc_Ntk_t * pNtk, int fCollectAll )
666 {
667 Vec_Ptr_t * vNodes;
668 Abc_Obj_t * pObj;
669 int i;
670 // set the traversal ID
671 Abc_NtkIncrementTravId( pNtk );
672 // start the array of nodes
673 vNodes = Vec_PtrAlloc( 100 );
674 Abc_NtkForEachPo( pNtk, pObj, i )
675 Abc_NtkDfsHie_rec( pObj, vNodes );
676 // collect dangling nodes if asked to
677 if ( fCollectAll )
678 {
679 Abc_NtkForEachObj( pNtk, pObj, i )
680 if ( !Abc_NodeIsTravIdCurrent(pObj) )
681 Abc_NtkDfs_rec( pObj, vNodes );
682 }
683 return vNodes;
684 }
685
686
687 /**Function*************************************************************
688
689 Synopsis [Returns 1 if the ordering of nodes is DFS.]
690
691 Description []
692
693 SideEffects []
694
695 SeeAlso []
696
697 ***********************************************************************/
Abc_NtkIsDfsOrdered(Abc_Ntk_t * pNtk)698 int Abc_NtkIsDfsOrdered( Abc_Ntk_t * pNtk )
699 {
700 Abc_Obj_t * pNode, * pFanin;
701 int i, k;
702 // set the traversal ID
703 Abc_NtkIncrementTravId( pNtk );
704 // mark the CIs
705 Abc_NtkForEachCi( pNtk, pNode, i )
706 Abc_NodeSetTravIdCurrent( pNode );
707 // go through the nodes
708 Abc_NtkForEachNode( pNtk, pNode, i )
709 {
710 // check the fanins of the node
711 Abc_ObjForEachFanin( pNode, pFanin, k )
712 if ( !Abc_NodeIsTravIdCurrent(pFanin) )
713 return 0;
714 // check the choices of the node
715 if ( Abc_NtkIsStrash(pNtk) && Abc_AigNodeIsChoice(pNode) )
716 for ( pFanin = (Abc_Obj_t *)pNode->pData; pFanin; pFanin = (Abc_Obj_t *)pFanin->pData )
717 if ( !Abc_NodeIsTravIdCurrent(pFanin) )
718 return 0;
719 // mark the node as visited
720 Abc_NodeSetTravIdCurrent( pNode );
721 }
722 return 1;
723 }
724
725 /**Function*************************************************************
726
727 Synopsis [Create DFS ordering of nets.]
728
729 Description []
730
731 SideEffects []
732
733 SeeAlso []
734
735 ***********************************************************************/
Abc_NtkDfsNets_rec(Abc_Obj_t * pNet,Vec_Ptr_t * vNets)736 void Abc_NtkDfsNets_rec( Abc_Obj_t * pNet, Vec_Ptr_t * vNets )
737 {
738 Abc_Obj_t * pNext;
739 Abc_Obj_t * pNode; int i;
740 assert( Abc_ObjIsNet(pNet) );
741 if ( Abc_NodeIsTravIdCurrent( pNet ) )
742 return;
743 Abc_NodeSetTravIdCurrent( pNet );
744 pNode = Abc_ObjFanin0( pNet );
745 Abc_ObjForEachFanin( pNode, pNext, i )
746 Abc_NtkDfsNets_rec( pNext, vNets );
747 Abc_ObjForEachFanout( pNode, pNext, i )
748 Vec_PtrPush( vNets, pNext );
749 }
Abc_NtkDfsNets(Abc_Ntk_t * pNtk)750 Vec_Ptr_t * Abc_NtkDfsNets( Abc_Ntk_t * pNtk )
751 {
752 Vec_Ptr_t * vNets;
753 Abc_Obj_t * pObj; int i;
754 vNets = Vec_PtrAlloc( 100 );
755 Abc_NtkIncrementTravId( pNtk );
756 Abc_NtkForEachCi( pNtk, pObj, i )
757 Abc_NodeSetTravIdCurrent( Abc_ObjFanout0(pObj) );
758 Abc_NtkForEachCi( pNtk, pObj, i )
759 Vec_PtrPush( vNets, Abc_ObjFanout0(pObj) );
760 Abc_NtkForEachCo( pNtk, pObj, i )
761 Abc_NtkDfsNets_rec( Abc_ObjFanin0(pObj), vNets );
762 return vNets;
763 }
764
765 /**Function*************************************************************
766
767 Synopsis [Returns the DFS ordered array of logic nodes.]
768
769 Description [Collects only the internal nodes, leaving out CIs and CO.
770 However it marks with the current TravId both CIs and COs.]
771
772 SideEffects []
773
774 SeeAlso []
775
776 ***********************************************************************/
Abc_NtkDfsWithBoxes_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)777 void Abc_NtkDfsWithBoxes_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
778 {
779 Abc_Obj_t * pFanin;
780 int i;
781 assert( !Abc_ObjIsNet(pNode) );
782 if ( Abc_ObjIsBo(pNode) )
783 pNode = Abc_ObjFanin0(pNode);
784 if ( Abc_ObjIsPi(pNode) )
785 return;
786 assert( Abc_ObjIsNode( pNode ) || Abc_ObjIsBox( pNode ) );
787 if ( Abc_NodeIsTravIdCurrent( pNode ) )
788 return;
789 Abc_NodeSetTravIdCurrent( pNode );
790 Abc_ObjForEachFanin( pNode, pFanin, i )
791 {
792 if ( Abc_ObjIsBox(pNode) )
793 pFanin = Abc_ObjFanin0(pFanin);
794 assert( Abc_ObjIsNet(pFanin) );
795 Abc_NtkDfsWithBoxes_rec( Abc_ObjFanin0Ntk(pFanin), vNodes );
796 }
797 Vec_PtrPush( vNodes, pNode );
798 }
Abc_NtkDfsWithBoxes(Abc_Ntk_t * pNtk)799 Vec_Ptr_t * Abc_NtkDfsWithBoxes( Abc_Ntk_t * pNtk )
800 {
801 Vec_Ptr_t * vNodes;
802 Abc_Obj_t * pObj;
803 int i;
804 Abc_NtkIncrementTravId( pNtk );
805 vNodes = Vec_PtrAlloc( 100 );
806 Abc_NtkForEachPo( pNtk, pObj, i )
807 {
808 assert( Abc_ObjIsNet(Abc_ObjFanin0(pObj)) );
809 Abc_NtkDfsWithBoxes_rec( Abc_ObjFanin0Ntk(Abc_ObjFanin0(pObj)), vNodes );
810 }
811 return vNodes;
812 }
813
814
815 /**Function*************************************************************
816
817 Synopsis [Performs DFS for one node.]
818
819 Description []
820
821 SideEffects []
822
823 SeeAlso []
824
825 ***********************************************************************/
Abc_NtkNodeSupport_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)826 void Abc_NtkNodeSupport_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
827 {
828 Abc_Obj_t * pFanin;
829 int i;
830 assert( !Abc_ObjIsNet(pNode) );
831 // if this node is already visited, skip
832 if ( Abc_NodeIsTravIdCurrent( pNode ) )
833 return;
834 // mark the node as visited
835 Abc_NodeSetTravIdCurrent( pNode );
836 // collect the CI
837 if ( Abc_ObjIsCi(pNode) || (Abc_NtkIsStrash(pNode->pNtk) && Abc_ObjFaninNum(pNode) == 0) )
838 {
839 Vec_PtrPush( vNodes, pNode );
840 return;
841 }
842 assert( Abc_ObjIsNode( pNode ) );
843 // visit the transitive fanin of the node
844 Abc_ObjForEachFanin( pNode, pFanin, i )
845 Abc_NtkNodeSupport_rec( Abc_ObjFanin0Ntk(pFanin), vNodes );
846 }
847
848 /**Function*************************************************************
849
850 Synopsis [Returns the set of CI nodes in the support of the given nodes.]
851
852 Description []
853
854 SideEffects []
855
856 SeeAlso []
857
858 ***********************************************************************/
Abc_NtkSupport(Abc_Ntk_t * pNtk)859 Vec_Ptr_t * Abc_NtkSupport( Abc_Ntk_t * pNtk )
860 {
861 Vec_Ptr_t * vNodes;
862 Abc_Obj_t * pNode;
863 int i;
864 // set the traversal ID
865 Abc_NtkIncrementTravId( pNtk );
866 // start the array of nodes
867 vNodes = Vec_PtrAlloc( 100 );
868 // go through the PO nodes and call for each of them
869 Abc_NtkForEachCo( pNtk, pNode, i )
870 Abc_NtkNodeSupport_rec( Abc_ObjFanin0(pNode), vNodes );
871 // add unused CIs
872 Abc_NtkForEachCi( pNtk, pNode, i )
873 if ( !Abc_NodeIsTravIdCurrent( pNode ) )
874 Vec_PtrPush( vNodes, pNode );
875 assert( Vec_PtrSize(vNodes) == Abc_NtkCiNum(pNtk) );
876 return vNodes;
877 }
878
879 /**Function*************************************************************
880
881 Synopsis [Returns the set of CI nodes in the support of the given nodes.]
882
883 Description []
884
885 SideEffects []
886
887 SeeAlso []
888
889 ***********************************************************************/
Abc_NtkNodeSupport(Abc_Ntk_t * pNtk,Abc_Obj_t ** ppNodes,int nNodes)890 Vec_Ptr_t * Abc_NtkNodeSupport( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppNodes, int nNodes )
891 {
892 Vec_Ptr_t * vNodes;
893 int i;
894 // set the traversal ID
895 Abc_NtkIncrementTravId( pNtk );
896 // start the array of nodes
897 vNodes = Vec_PtrAlloc( 100 );
898 // go through the PO nodes and call for each of them
899 for ( i = 0; i < nNodes; i++ )
900 if ( Abc_ObjIsCo(ppNodes[i]) )
901 Abc_NtkNodeSupport_rec( Abc_ObjFanin0(ppNodes[i]), vNodes );
902 else
903 Abc_NtkNodeSupport_rec( ppNodes[i], vNodes );
904 return vNodes;
905 }
906
907 /**Function*************************************************************
908
909 Synopsis [Returns the set of CI node IDs in the support of the given node.]
910
911 Description []
912
913 SideEffects []
914
915 SeeAlso []
916
917 ***********************************************************************/
Abc_NtkNodeSupportInt_rec(Abc_Obj_t * pNode,Vec_Int_t * vNodes)918 void Abc_NtkNodeSupportInt_rec( Abc_Obj_t * pNode, Vec_Int_t * vNodes )
919 {
920 Abc_Obj_t * pFanin;
921 int i;
922 assert( !Abc_ObjIsNet(pNode) );
923 // if this node is already visited, skip
924 if ( Abc_NodeIsTravIdCurrent( pNode ) )
925 return;
926 // mark the node as visited
927 Abc_NodeSetTravIdCurrent( pNode );
928 // collect the CI
929 if ( Abc_ObjIsCi(pNode) || (Abc_NtkIsStrash(pNode->pNtk) && Abc_ObjFaninNum(pNode) == 0) )
930 {
931 if ( Abc_ObjIsCi(pNode) )
932 Vec_IntPush( vNodes, pNode->iTemp );
933 return;
934 }
935 assert( Abc_ObjIsNode( pNode ) );
936 // visit the transitive fanin of the node
937 Abc_ObjForEachFanin( pNode, pFanin, i )
938 Abc_NtkNodeSupportInt_rec( Abc_ObjFanin0Ntk(pFanin), vNodes );
939 }
Abc_NtkNodeSupportInt(Abc_Ntk_t * pNtk,int iCo)940 Vec_Int_t * Abc_NtkNodeSupportInt( Abc_Ntk_t * pNtk, int iCo )
941 {
942 Vec_Int_t * vNodes;
943 Abc_Obj_t * pObj;
944 int i;
945 if ( iCo < 0 || iCo >= Abc_NtkCoNum(pNtk) )
946 return NULL;
947 // save node indices in the CI nodes
948 Abc_NtkForEachCi( pNtk, pObj, i )
949 pObj->iTemp = i;
950 // collect the indexes of CI nodes in the TFI of the CO node
951 Abc_NtkIncrementTravId( pNtk );
952 pObj = Abc_NtkCo( pNtk, iCo );
953 vNodes = Vec_IntAlloc( 100 );
954 Abc_NtkNodeSupportInt_rec( Abc_ObjFanin0(pObj), vNodes );
955 Vec_IntSort( vNodes, 0 );
956 return vNodes;
957 }
958
959 /**Function*************************************************************
960
961 Synopsis [Derives GIA comparing two outputs.]
962
963 Description []
964
965 SideEffects []
966
967 SeeAlso []
968
969 ***********************************************************************/
Abc_NtkFunctionalIsoGia_rec(Gia_Man_t * pNew,Abc_Obj_t * pNode)970 int Abc_NtkFunctionalIsoGia_rec( Gia_Man_t * pNew, Abc_Obj_t * pNode )
971 {
972 int iLit0, iLit1;
973 if ( Abc_NodeIsTravIdCurrent(pNode) || Abc_ObjFaninNum(pNode) == 0 || Abc_ObjIsCi(pNode) )
974 return pNode->iTemp;
975 assert( Abc_ObjIsNode( pNode ) );
976 Abc_NodeSetTravIdCurrent( pNode );
977 iLit0 = Abc_NtkFunctionalIsoGia_rec( pNew, Abc_ObjFanin0(pNode) );
978 iLit1 = Abc_NtkFunctionalIsoGia_rec( pNew, Abc_ObjFanin1(pNode) );
979 iLit0 = Abc_LitNotCond( iLit0, Abc_ObjFaninC0(pNode) );
980 iLit1 = Abc_LitNotCond( iLit1, Abc_ObjFaninC1(pNode) );
981 return (pNode->iTemp = Gia_ManHashAnd(pNew, iLit0, iLit1));
982 }
Abc_NtkFunctionalIsoGia(Abc_Ntk_t * pNtk,int iCo1,int iCo2,int fCommon)983 Gia_Man_t * Abc_NtkFunctionalIsoGia( Abc_Ntk_t * pNtk, int iCo1, int iCo2, int fCommon )
984 {
985 Gia_Man_t * pNew = NULL, * pTemp;
986 Vec_Int_t * vSupp1 = Abc_NtkNodeSupportInt( pNtk, iCo1 );
987 Vec_Int_t * vSupp2 = Abc_NtkNodeSupportInt( pNtk, iCo2 );
988 if ( Vec_IntSize(vSupp1) == Vec_IntSize(vSupp2) )
989 {
990 Abc_Obj_t * pObj;
991 int i, iCi, iLit1, iLit2;
992 pNew = Gia_ManStart( 1000 );
993 pNew->pName = Abc_UtilStrsav( pNtk->pName );
994 pNew->pSpec = Abc_UtilStrsav( pNtk->pSpec );
995 Gia_ManHashStart( pNew );
996 // put commom together
997 if ( fCommon )
998 {
999 Vec_Int_t * vCommon = Vec_IntAlloc( Vec_IntSize(vSupp1) );
1000 Vec_IntTwoRemoveCommon( vSupp1, vSupp2, vCommon );
1001 Vec_IntAppend( vSupp1, vCommon );
1002 Vec_IntAppend( vSupp2, vCommon );
1003 Vec_IntFree( vCommon );
1004 assert( Vec_IntSize(vSupp1) == Vec_IntSize(vSupp2) );
1005 }
1006 // primary inputs
1007 Abc_AigConst1(pNtk)->iTemp = 1;
1008 Vec_IntForEachEntry( vSupp1, iCi, i )
1009 Abc_NtkCi(pNtk, iCi)->iTemp = Gia_ManAppendCi(pNew);
1010 // create the first cone
1011 Abc_NtkIncrementTravId( pNtk );
1012 pObj = Abc_NtkCo( pNtk, iCo1 );
1013 iLit1 = Abc_NtkFunctionalIsoGia_rec( pNew, Abc_ObjFanin0(pObj) );
1014 iLit1 = Abc_LitNotCond( iLit1, Abc_ObjFaninC0(pObj) );
1015 // primary inputs
1016 Vec_IntForEachEntry( vSupp2, iCi, i )
1017 Abc_NtkCi(pNtk, iCi)->iTemp = Gia_ManCiLit(pNew, i);
1018 // create the second cone
1019 Abc_NtkIncrementTravId( pNtk );
1020 pObj = Abc_NtkCo( pNtk, iCo2 );
1021 iLit2 = Abc_NtkFunctionalIsoGia_rec( pNew, Abc_ObjFanin0(pObj) );
1022 iLit2 = Abc_LitNotCond( iLit2, Abc_ObjFaninC0(pObj) );
1023 Gia_ManAppendCo( pNew, iLit1 );
1024 Gia_ManAppendCo( pNew, iLit2 );
1025 // perform cleanup
1026 pNew = Gia_ManCleanup( pTemp = pNew );
1027 Gia_ManStop( pTemp );
1028 }
1029 Vec_IntFree( vSupp1 );
1030 Vec_IntFree( vSupp2 );
1031 return pNew;
1032 }
Abc_NtkFunctionalIsoInt(Abc_Ntk_t * pNtk,int iCo1,int iCo2,int fCommon)1033 int Abc_NtkFunctionalIsoInt( Abc_Ntk_t * pNtk, int iCo1, int iCo2, int fCommon )
1034 {
1035 Gia_Man_t * pGia; int Value;
1036 assert( Abc_NtkIsStrash(pNtk) );
1037 if ( iCo1 < 0 || iCo1 >= Abc_NtkCoNum(pNtk) )
1038 return 0;
1039 if ( iCo2 < 0 || iCo2 >= Abc_NtkCoNum(pNtk) )
1040 return 0;
1041 pGia = Abc_NtkFunctionalIsoGia( pNtk, iCo1, iCo2, fCommon );
1042 if ( pGia == NULL )
1043 return 0;
1044 Value = Cec_ManVerifySimple( pGia );
1045 Gia_ManStop( pGia );
1046 return (int)(Value == 1);
1047 }
Abc_NtkFunctionalIso(Abc_Ntk_t * pNtk,int iCo1,int iCo2,int fCommon)1048 int Abc_NtkFunctionalIso( Abc_Ntk_t * pNtk, int iCo1, int iCo2, int fCommon )
1049 {
1050 Abc_Ntk_t * pNtkNew; int Result;
1051 if ( Abc_NtkIsStrash(pNtk) )
1052 return Abc_NtkFunctionalIsoInt( pNtk, iCo1, iCo2, fCommon );
1053 pNtkNew = Abc_NtkStrash( pNtk, 0, 0, 0 );
1054 Result = Abc_NtkFunctionalIsoInt( pNtkNew, iCo1, iCo2, fCommon );
1055 Abc_NtkDelete( pNtkNew );
1056 return Result;
1057 }
1058
1059
1060 /**Function*************************************************************
1061
1062 Synopsis [Computes support size of the node.]
1063
1064 Description []
1065
1066 SideEffects []
1067
1068 SeeAlso []
1069
1070 ***********************************************************************/
Abc_ObjSuppSize_rec(Abc_Obj_t * pObj)1071 int Abc_ObjSuppSize_rec( Abc_Obj_t * pObj )
1072 {
1073 Abc_Obj_t * pFanin;
1074 int i, Counter = 0;
1075 if ( Abc_NodeIsTravIdCurrent(pObj) )
1076 return 0;
1077 Abc_NodeSetTravIdCurrent(pObj);
1078 if ( Abc_ObjIsPi(pObj) )
1079 return 1;
1080 assert( Abc_ObjIsNode(pObj) || Abc_ObjIsBox(pObj) );
1081 Abc_ObjForEachFanin( pObj, pFanin, i )
1082 Counter += Abc_ObjSuppSize_rec( pFanin );
1083 return Counter;
1084 }
1085 /**Function*************************************************************
1086
1087 Synopsis [Computes support size of the node.]
1088
1089 Description []
1090
1091 SideEffects []
1092
1093 SeeAlso []
1094
1095 ***********************************************************************/
Abc_ObjSuppSize(Abc_Obj_t * pObj)1096 int Abc_ObjSuppSize( Abc_Obj_t * pObj )
1097 {
1098 Abc_NtkIncrementTravId( Abc_ObjNtk(pObj) );
1099 return Abc_ObjSuppSize_rec( pObj );
1100 }
1101 /**Function*************************************************************
1102
1103 Synopsis [Computes support size of the node.]
1104
1105 Description []
1106
1107 SideEffects []
1108
1109 SeeAlso []
1110
1111 ***********************************************************************/
Abc_NtkSuppSizeTest(Abc_Ntk_t * p)1112 int Abc_NtkSuppSizeTest( Abc_Ntk_t * p )
1113 {
1114 Abc_Obj_t * pObj;
1115 int i, Counter = 0;
1116 abctime clk = Abc_Clock();
1117 Abc_NtkForEachObj( p, pObj, i )
1118 if ( Abc_ObjIsNode(pObj) )
1119 Counter += (Abc_ObjSuppSize(pObj) <= 16);
1120 printf( "Nodes with small support %d (out of %d)\n", Counter, Abc_NtkNodeNum(p) );
1121 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
1122 return Counter;
1123 }
1124
1125 /**Function*************************************************************
1126
1127 Synopsis [Computes the sum total of supports of all outputs.]
1128
1129 Description []
1130
1131 SideEffects []
1132
1133 SeeAlso []
1134
1135 ***********************************************************************/
Abc_NtkSupportSum(Abc_Ntk_t * pNtk)1136 void Abc_NtkSupportSum( Abc_Ntk_t * pNtk )
1137 {
1138 Vec_Ptr_t * vSupp;
1139 Abc_Obj_t * pObj;
1140 int i, nTotalSupps = 0;
1141 Abc_NtkForEachCo( pNtk, pObj, i )
1142 {
1143 vSupp = Abc_NtkNodeSupport( pNtk, &pObj, 1 );
1144 nTotalSupps += Vec_PtrSize( vSupp );
1145 Vec_PtrFree( vSupp );
1146 }
1147 printf( "Total supports = %d.\n", nTotalSupps );
1148 }
1149
1150
1151 /**Function*************************************************************
1152
1153 Synopsis [Performs DFS for one node.]
1154
1155 Description []
1156
1157 SideEffects []
1158
1159 SeeAlso []
1160
1161 ***********************************************************************/
Abc_AigDfs_rec(Abc_Obj_t * pNode,Vec_Ptr_t * vNodes)1162 void Abc_AigDfs_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
1163 {
1164 Abc_Obj_t * pFanin;
1165 int i;
1166 // if this node is already visited, skip
1167 if ( Abc_NodeIsTravIdCurrent( pNode ) )
1168 return;
1169 // mark the node as visited
1170 Abc_NodeSetTravIdCurrent( pNode );
1171 // skip the PI
1172 if ( Abc_ObjIsCi(pNode) || Abc_AigNodeIsConst(pNode) )
1173 return;
1174 assert( Abc_ObjIsNode( pNode ) );
1175 // visit the transitive fanin of the node
1176 Abc_ObjForEachFanin( pNode, pFanin, i )
1177 Abc_AigDfs_rec( pFanin, vNodes );
1178 // visit the equivalent nodes
1179 if ( Abc_AigNodeIsChoice( pNode ) )
1180 for ( pFanin = (Abc_Obj_t *)pNode->pData; pFanin; pFanin = (Abc_Obj_t *)pFanin->pData )
1181 Abc_AigDfs_rec( pFanin, vNodes );
1182 // add the node after the fanins have been added
1183 Vec_PtrPush( vNodes, pNode );
1184 }
1185
1186 /**Function*************************************************************
1187
1188 Synopsis [Returns the DFS ordered array of logic nodes.]
1189
1190 Description [Collects only the internal nodes, leaving out CIs/COs.
1191 However it marks both CIs and COs with the current TravId.]
1192
1193 SideEffects []
1194
1195 SeeAlso []
1196
1197 ***********************************************************************/
Abc_AigDfs(Abc_Ntk_t * pNtk,int fCollectAll,int fCollectCos)1198 Vec_Ptr_t * Abc_AigDfs( Abc_Ntk_t * pNtk, int fCollectAll, int fCollectCos )
1199 {
1200 Vec_Ptr_t * vNodes;
1201 Abc_Obj_t * pNode;
1202 int i;
1203 assert( Abc_NtkIsStrash(pNtk) );
1204 // set the traversal ID
1205 Abc_NtkIncrementTravId( pNtk );
1206 // start the array of nodes
1207 vNodes = Vec_PtrAlloc( 100 );
1208 // go through the PO nodes and call for each of them
1209 Abc_NtkForEachCo( pNtk, pNode, i )
1210 {
1211 Abc_AigDfs_rec( Abc_ObjFanin0(pNode), vNodes );
1212 Abc_NodeSetTravIdCurrent( pNode );
1213 if ( fCollectCos )
1214 Vec_PtrPush( vNodes, pNode );
1215 }
1216 // collect dangling nodes if asked to
1217 if ( fCollectAll )
1218 {
1219 Abc_NtkForEachNode( pNtk, pNode, i )
1220 if ( !Abc_NodeIsTravIdCurrent(pNode) )
1221 Abc_AigDfs_rec( pNode, vNodes );
1222 }
1223 return vNodes;
1224 }
1225
1226 /**Function*************************************************************
1227
1228 Synopsis [Returns the DFS ordered array of logic nodes.]
1229
1230 Description [Collects only the internal nodes, leaving out CIs/COs.
1231 However it marks both CIs and COs with the current TravId.]
1232
1233 SideEffects []
1234
1235 SeeAlso []
1236
1237 ***********************************************************************/
Abc_AigDfsMap(Abc_Ntk_t * pNtk)1238 Vec_Ptr_t * Abc_AigDfsMap( Abc_Ntk_t * pNtk )
1239 {
1240 Vec_Ptr_t * vNodes;
1241 Abc_Obj_t * pNode;
1242 int i;
1243 assert( Abc_NtkIsStrash(pNtk) );
1244 // set the traversal ID
1245 Abc_NtkIncrementTravId( pNtk );
1246 // start the array of nodes
1247 vNodes = Vec_PtrAlloc( 100 );
1248 // collect cones of barbufs
1249 Abc_NtkForEachCo( pNtk, pNode, i )
1250 {
1251 if ( i < Abc_NtkCoNum(pNtk) - pNtk->nBarBufs )
1252 continue;
1253 Abc_AigDfs_rec( Abc_ObjFanin0(pNode), vNodes );
1254 Abc_NodeSetTravIdCurrent( pNode );
1255 // collect latch as a placeholder
1256 assert( Abc_ObjIsLatch(Abc_ObjFanout0(pNode)) );
1257 Vec_PtrPush( vNodes, Abc_ObjFanout0(pNode) );
1258 }
1259 // collect nodes of real POs
1260 Abc_NtkForEachCo( pNtk, pNode, i )
1261 {
1262 if ( i >= Abc_NtkCoNum(pNtk) - pNtk->nBarBufs )
1263 break;
1264 Abc_AigDfs_rec( Abc_ObjFanin0(pNode), vNodes );
1265 assert( Abc_ObjIsCo(pNode) );
1266 Abc_NodeSetTravIdCurrent( pNode );
1267 }
1268 return vNodes;
1269 }
1270
1271 /**Function*************************************************************
1272
1273 Synopsis [Collects nodes in the DFS manner by level.]
1274
1275 Description [The number of levels should be set!!!]
1276
1277 SideEffects []
1278
1279 SeeAlso []
1280
1281 ***********************************************************************/
Abc_DfsLevelizedTfo_rec(Abc_Obj_t * pNode,Vec_Vec_t * vLevels)1282 void Abc_DfsLevelizedTfo_rec( Abc_Obj_t * pNode, Vec_Vec_t * vLevels )
1283 {
1284 Abc_Obj_t * pFanout;
1285 int i;
1286 // if this node is already visited, skip
1287 if ( Abc_NodeIsTravIdCurrent( pNode ) )
1288 return;
1289 // mark the node as visited
1290 Abc_NodeSetTravIdCurrent( pNode );
1291 // skip the terminals
1292 if ( Abc_ObjIsCo(pNode) )
1293 return;
1294 assert( Abc_ObjIsNode(pNode) );
1295 // add the node to the structure
1296 Vec_VecPush( vLevels, pNode->Level, pNode );
1297 // visit the TFO
1298 Abc_ObjForEachFanout( pNode, pFanout, i )
1299 Abc_DfsLevelizedTfo_rec( pFanout, vLevels );
1300 }
1301
1302 /**Function*************************************************************
1303
1304 Synopsis [Collects nodes in the DFS manner by level.]
1305
1306 Description [The number of levels should be set!!!]
1307
1308 SideEffects []
1309
1310 SeeAlso []
1311
1312 ***********************************************************************/
Abc_DfsLevelized(Abc_Obj_t * pNode,int fTfi)1313 Vec_Vec_t * Abc_DfsLevelized( Abc_Obj_t * pNode, int fTfi )
1314 {
1315 Vec_Vec_t * vLevels;
1316 Abc_Obj_t * pFanout;
1317 int i;
1318 assert( fTfi == 0 );
1319 assert( !Abc_NtkIsNetlist(pNode->pNtk) );
1320 // set the traversal ID
1321 Abc_NtkIncrementTravId( pNode->pNtk );
1322 vLevels = Vec_VecAlloc( 100 );
1323 if ( Abc_ObjIsNode(pNode) )
1324 Abc_DfsLevelizedTfo_rec( pNode, vLevels );
1325 else
1326 {
1327 assert( Abc_ObjIsCi(pNode) );
1328 Abc_NodeSetTravIdCurrent( pNode );
1329 Abc_ObjForEachFanout( pNode, pFanout, i )
1330 Abc_DfsLevelizedTfo_rec( pFanout, vLevels );
1331 }
1332 return vLevels;
1333 }
1334
1335
1336 /**Function*************************************************************
1337
1338 Synopsis [Recursively counts the number of logic levels of one node.]
1339
1340 Description []
1341
1342 SideEffects []
1343
1344 SeeAlso []
1345
1346 ***********************************************************************/
Abc_NtkLevel_rec(Abc_Obj_t * pNode)1347 int Abc_NtkLevel_rec( Abc_Obj_t * pNode )
1348 {
1349 Abc_Obj_t * pNext;
1350 int i, Level;
1351 assert( !Abc_ObjIsNet(pNode) );
1352 // skip the PI
1353 if ( Abc_ObjIsCi(pNode) )
1354 return pNode->Level;
1355 assert( Abc_ObjIsNode( pNode ) || pNode->Type == ABC_OBJ_CONST1);
1356 // if this node is already visited, return
1357 if ( Abc_NodeIsTravIdCurrent( pNode ) )
1358 return pNode->Level;
1359 // mark the node as visited
1360 Abc_NodeSetTravIdCurrent( pNode );
1361 // visit the transitive fanin
1362 pNode->Level = 0;
1363 Abc_ObjForEachFanin( pNode, pNext, i )
1364 {
1365 Level = Abc_NtkLevel_rec( Abc_ObjFanin0Ntk(pNext) );
1366 if ( pNode->Level < (unsigned)Level )
1367 pNode->Level = Level;
1368 }
1369 if ( Abc_ObjFaninNum(pNode) > 0 && !Abc_ObjIsBarBuf(pNode) )
1370 pNode->Level++;
1371 return pNode->Level;
1372 }
1373
1374 /**Function*************************************************************
1375
1376 Synopsis [Recursively counts the number of logic levels of one node.]
1377
1378 Description []
1379
1380 SideEffects []
1381
1382 SeeAlso []
1383
1384 ***********************************************************************/
Abc_NtkLevelReverse_rec(Abc_Obj_t * pNode)1385 int Abc_NtkLevelReverse_rec( Abc_Obj_t * pNode )
1386 {
1387 Abc_Obj_t * pNext;
1388 int i, Level;
1389 assert( !Abc_ObjIsNet(pNode) );
1390 // skip the PI
1391 if ( Abc_ObjIsCo(pNode) )
1392 return pNode->Level;
1393 assert( Abc_ObjIsNode( pNode ) || pNode->Type == ABC_OBJ_CONST1);
1394 // if this node is already visited, return
1395 if ( Abc_NodeIsTravIdCurrent( pNode ) )
1396 return pNode->Level;
1397 // mark the node as visited
1398 Abc_NodeSetTravIdCurrent( pNode );
1399 // visit the transitive fanin
1400 pNode->Level = 0;
1401 Abc_ObjForEachFanout( pNode, pNext, i )
1402 {
1403 Level = Abc_NtkLevelReverse_rec( Abc_ObjFanout0Ntk(pNext) );
1404 if ( pNode->Level < (unsigned)Level )
1405 pNode->Level = Level;
1406 }
1407 if ( Abc_ObjFaninNum(pNode) > 0 && !Abc_ObjIsBarBuf(pNode) )
1408 pNode->Level++;
1409 return pNode->Level;
1410 }
1411
1412 /**Function*************************************************************
1413
1414 Synopsis [Computes the number of logic levels not counting PIs/POs.]
1415
1416 Description []
1417
1418 SideEffects []
1419
1420 SeeAlso []
1421
1422 ***********************************************************************/
Abc_NtkLevelize(Abc_Ntk_t * pNtk)1423 Vec_Vec_t * Abc_NtkLevelize( Abc_Ntk_t * pNtk )
1424 {
1425 Abc_Obj_t * pObj;
1426 Vec_Vec_t * vLevels;
1427 int nLevels, i;
1428 nLevels = Abc_NtkLevel( pNtk );
1429 vLevels = Vec_VecStart( nLevels + 1 );
1430 Abc_NtkForEachNode( pNtk, pObj, i )
1431 {
1432 assert( (int)pObj->Level <= nLevels );
1433 Vec_VecPush( vLevels, pObj->Level, pObj );
1434 }
1435 return vLevels;
1436 }
1437
1438 /**Function*************************************************************
1439
1440 Synopsis [Computes the number of logic levels not counting PIs/POs.]
1441
1442 Description []
1443
1444 SideEffects []
1445
1446 SeeAlso []
1447
1448 ***********************************************************************/
Abc_NtkLevel(Abc_Ntk_t * pNtk)1449 int Abc_NtkLevel( Abc_Ntk_t * pNtk )
1450 {
1451 Abc_Obj_t * pNode;
1452 int i, LevelsMax;
1453 // set the CI levels
1454 if ( pNtk->pManTime == NULL || pNtk->AndGateDelay <= 0 )
1455 Abc_NtkForEachCi( pNtk, pNode, i )
1456 pNode->Level = 0;
1457 else
1458 Abc_NtkForEachCi( pNtk, pNode, i )
1459 pNode->Level = (int)(Abc_MaxFloat(0, Abc_NodeReadArrivalWorst(pNode)) / pNtk->AndGateDelay);
1460 // perform the traversal
1461 LevelsMax = 0;
1462 Abc_NtkIncrementTravId( pNtk );
1463 if ( pNtk->nBarBufs == 0 )
1464 {
1465 Abc_NtkForEachNode( pNtk, pNode, i )
1466 {
1467 Abc_NtkLevel_rec( pNode );
1468 if ( LevelsMax < (int)pNode->Level )
1469 LevelsMax = (int)pNode->Level;
1470 }
1471 }
1472 else
1473 {
1474 Abc_NtkForEachLiPo( pNtk, pNode, i )
1475 {
1476 Abc_Obj_t * pDriver = Abc_ObjFanin0(pNode);
1477 Abc_NtkLevel_rec( pDriver );
1478 if ( LevelsMax < (int)pDriver->Level )
1479 LevelsMax = (int)pDriver->Level;
1480 // transfer the delay
1481 if ( i < pNtk->nBarBufs )
1482 Abc_ObjFanout0(Abc_ObjFanout0(pNode))->Level = pDriver->Level;
1483 }
1484 }
1485 return LevelsMax;
1486 }
1487
1488 /**Function*************************************************************
1489
1490 Synopsis [Computes the number of logic levels not counting PIs/POs.]
1491
1492 Description []
1493
1494 SideEffects []
1495
1496 SeeAlso []
1497
1498 ***********************************************************************/
Abc_NtkLevelReverse(Abc_Ntk_t * pNtk)1499 int Abc_NtkLevelReverse( Abc_Ntk_t * pNtk )
1500 {
1501 Abc_Obj_t * pNode;
1502 int i, LevelsMax;
1503 // set the CO levels to zero
1504 Abc_NtkForEachCo( pNtk, pNode, i )
1505 pNode->Level = 0;
1506 // perform the traversal
1507 LevelsMax = 0;
1508 Abc_NtkIncrementTravId( pNtk );
1509 Abc_NtkForEachNode( pNtk, pNode, i )
1510 {
1511 Abc_NtkLevelReverse_rec( pNode );
1512 if ( LevelsMax < (int)pNode->Level )
1513 LevelsMax = (int)pNode->Level;
1514 }
1515 return LevelsMax;
1516 }
1517
1518
1519 /**Function*************************************************************
1520
1521 Synopsis [Recursively detects combinational loops.]
1522
1523 Description []
1524
1525 SideEffects []
1526
1527 SeeAlso []
1528
1529 ***********************************************************************/
Abc_NtkIsAcyclic_rec(Abc_Obj_t * pNode)1530 int Abc_NtkIsAcyclic_rec( Abc_Obj_t * pNode )
1531 {
1532 Abc_Ntk_t * pNtk = pNode->pNtk;
1533 Abc_Obj_t * pFanin;
1534 int fAcyclic, i;
1535 assert( !Abc_ObjIsNet(pNode) );
1536 if ( Abc_ObjIsCi(pNode) || Abc_ObjIsBox(pNode) || (Abc_NtkIsStrash(pNode->pNtk) && Abc_AigNodeIsConst(pNode)) )
1537 return 1;
1538 assert( Abc_ObjIsNode(pNode) );
1539 // make sure the node is not visited
1540 assert( !Abc_NodeIsTravIdPrevious(pNode) );
1541 // check if the node is part of the combinational loop
1542 if ( Abc_NodeIsTravIdCurrent(pNode) )
1543 {
1544 fprintf( stdout, "Network \"%s\" contains combinational loop!\n", Abc_NtkName(pNtk) );
1545 fprintf( stdout, "Node \"%s\" is encountered twice on the following path to the COs:\n", Abc_ObjName(pNode) );
1546 return 0;
1547 }
1548 // mark this node as a node on the current path
1549 Abc_NodeSetTravIdCurrent( pNode );
1550 // visit the transitive fanin
1551 Abc_ObjForEachFanin( pNode, pFanin, i )
1552 {
1553 pFanin = Abc_ObjFanin0Ntk(pFanin);
1554 // make sure there is no mixing of networks
1555 assert( pFanin->pNtk == pNode->pNtk );
1556 // check if the fanin is visited
1557 if ( Abc_NodeIsTravIdPrevious(pFanin) )
1558 continue;
1559 // traverse the fanin's cone searching for the loop
1560 if ( (fAcyclic = Abc_NtkIsAcyclic_rec(pFanin)) )
1561 continue;
1562 // return as soon as the loop is detected
1563 fprintf( stdout, " %s ->", Abc_ObjName(pFanin) );
1564 return 0;
1565 }
1566 // visit choices
1567 if ( Abc_NtkIsStrash(pNode->pNtk) && Abc_AigNodeIsChoice(pNode) )
1568 {
1569 for ( pFanin = (Abc_Obj_t *)pNode->pData; pFanin; pFanin = (Abc_Obj_t *)pFanin->pData )
1570 {
1571 // check if the fanin is visited
1572 if ( Abc_NodeIsTravIdPrevious(pFanin) )
1573 continue;
1574 // traverse the fanin's cone searching for the loop
1575 if ( (fAcyclic = Abc_NtkIsAcyclic_rec(pFanin)) )
1576 continue;
1577 // return as soon as the loop is detected
1578 fprintf( stdout, " %s", Abc_ObjName(pFanin) );
1579 fprintf( stdout, " (choice of %s) -> ", Abc_ObjName(pNode) );
1580 return 0;
1581 }
1582 }
1583 // mark this node as a visited node
1584 Abc_NodeSetTravIdPrevious( pNode );
1585 return 1;
1586 }
1587
1588 /**Function*************************************************************
1589
1590 Synopsis [Detects combinational loops.]
1591
1592 Description [This procedure is based on the idea suggested by Donald Chai.
1593 As we traverse the network and visit the nodes, we need to distinquish
1594 three types of nodes: (1) those that are visited for the first time,
1595 (2) those that have been visited in this traversal but are currently not
1596 on the traversal path, (3) those that have been visited and are currently
1597 on the travesal path. When the node of type (3) is encountered, it means
1598 that there is a combinational loop. To mark the three types of nodes,
1599 two new values of the traversal IDs are used.]
1600
1601 SideEffects []
1602
1603 SeeAlso []
1604
1605 ***********************************************************************/
Abc_NtkIsAcyclic(Abc_Ntk_t * pNtk)1606 int Abc_NtkIsAcyclic( Abc_Ntk_t * pNtk )
1607 {
1608 Abc_Obj_t * pNode;
1609 int fAcyclic;
1610 int i;
1611 // set the traversal ID for this DFS ordering
1612 Abc_NtkIncrementTravId( pNtk );
1613 Abc_NtkIncrementTravId( pNtk );
1614 // pNode->TravId == pNet->nTravIds means "pNode is on the path"
1615 // pNode->TravId == pNet->nTravIds - 1 means "pNode is visited but is not on the path"
1616 // pNode->TravId < pNet->nTravIds - 1 means "pNode is not visited"
1617 // traverse the network to detect cycles
1618 fAcyclic = 1;
1619 Abc_NtkForEachCo( pNtk, pNode, i )
1620 {
1621 pNode = Abc_ObjFanin0Ntk(Abc_ObjFanin0(pNode));
1622 if ( Abc_NodeIsTravIdPrevious(pNode) )
1623 continue;
1624 // traverse the output logic cone
1625 if ( (fAcyclic = Abc_NtkIsAcyclic_rec(pNode)) )
1626 continue;
1627 // stop as soon as the first loop is detected
1628 fprintf( stdout, " CO \"%s\"\n", Abc_ObjName(Abc_ObjFanout0(pNode)) );
1629 break;
1630 }
1631 return fAcyclic;
1632 }
1633
1634 /**Function*************************************************************
1635
1636 Synopsis [Checks for the loops with boxes.]
1637
1638 Description []
1639
1640 SideEffects []
1641
1642 SeeAlso []
1643
1644 ***********************************************************************/
Abc_NtkIsAcyclicWithBoxes_rec(Abc_Obj_t * pNode)1645 int Abc_NtkIsAcyclicWithBoxes_rec( Abc_Obj_t * pNode )
1646 {
1647 Abc_Ntk_t * pNtk = pNode->pNtk;
1648 Abc_Obj_t * pFanin;
1649 int fAcyclic, i;
1650 assert( !Abc_ObjIsNet(pNode) );
1651 if ( Abc_ObjIsPi(pNode) || Abc_ObjIsLatch(pNode) || Abc_ObjIsBlackbox(pNode) )
1652 return 1;
1653 assert( Abc_ObjIsNode(pNode) || Abc_ObjIsBox(pNode) );
1654 // make sure the node is not visited
1655 assert( !Abc_NodeIsTravIdPrevious(pNode) );
1656 // check if the node is part of the combinational loop
1657 if ( Abc_NodeIsTravIdCurrent(pNode) )
1658 {
1659 fprintf( stdout, "Network \"%s\" contains combinational loop!\n", Abc_NtkName(pNtk) );
1660 if ( Abc_ObjIsBox(pNode) )
1661 fprintf( stdout, "Box \"%s\" is encountered twice on the following path to the COs:\n", Abc_ObjName(pNode) );
1662 else
1663 fprintf( stdout, "Node \"%s\" is encountered twice on the following path to the COs:\n", Abc_ObjName(Abc_ObjFanout0(pNode)) );
1664 return 0;
1665 }
1666 // mark this node as a node on the current path
1667 Abc_NodeSetTravIdCurrent( pNode );
1668 // visit the transitive fanin
1669 Abc_ObjForEachFanin( pNode, pFanin, i )
1670 {
1671 if ( Abc_ObjIsBox(pNode) )
1672 pFanin = Abc_ObjFanin0(pFanin);
1673 pFanin = Abc_ObjFanin0Ntk(pFanin);
1674 if ( Abc_ObjIsBo(pFanin) )
1675 pFanin = Abc_ObjFanin0(pFanin);
1676 // check if the fanin is visited
1677 if ( Abc_ObjIsPi(pFanin) || Abc_ObjIsLatch(pFanin) || Abc_ObjIsBlackbox(pFanin) )
1678 continue;
1679 assert( Abc_ObjIsNode(pFanin) || Abc_ObjIsBox(pFanin) );
1680 if ( Abc_NodeIsTravIdPrevious(pFanin) )
1681 continue;
1682 // traverse the fanin's cone searching for the loop
1683 if ( (fAcyclic = Abc_NtkIsAcyclicWithBoxes_rec(pFanin)) )
1684 continue;
1685 // return as soon as the loop is detected
1686 fprintf( stdout, " %s ->", Abc_ObjName( Abc_ObjIsBox(pFanin) ? pFanin : Abc_ObjFanout0(pFanin) ) );
1687 return 0;
1688 }
1689 // mark this node as a visited node
1690 assert( Abc_ObjIsNode(pNode) || Abc_ObjIsBox(pNode) );
1691 Abc_NodeSetTravIdPrevious( pNode );
1692 return 1;
1693 }
Abc_NtkIsAcyclicWithBoxes(Abc_Ntk_t * pNtk)1694 int Abc_NtkIsAcyclicWithBoxes( Abc_Ntk_t * pNtk )
1695 {
1696 Abc_Obj_t * pNode;
1697 int fAcyclic;
1698 int i;
1699 // set the traversal ID for this DFS ordering
1700 Abc_NtkIncrementTravId( pNtk );
1701 Abc_NtkIncrementTravId( pNtk );
1702 // pNode->TravId == pNet->nTravIds means "pNode is on the path"
1703 // pNode->TravId == pNet->nTravIds - 1 means "pNode is visited but is not on the path"
1704 // pNode->TravId < pNet->nTravIds - 1 means "pNode is not visited"
1705 // traverse the network to detect cycles
1706 fAcyclic = 1;
1707 Abc_NtkForEachPo( pNtk, pNode, i )
1708 {
1709 pNode = Abc_ObjFanin0Ntk(Abc_ObjFanin0(pNode));
1710 if ( Abc_ObjIsBo(pNode) )
1711 pNode = Abc_ObjFanin0(pNode);
1712 if ( Abc_NodeIsTravIdPrevious(pNode) )
1713 continue;
1714 // traverse the output logic cone
1715 if ( (fAcyclic = Abc_NtkIsAcyclicWithBoxes_rec(pNode)) )
1716 continue;
1717 // stop as soon as the first loop is detected
1718 fprintf( stdout, " PO \"%s\"\n", Abc_ObjName(Abc_ObjFanout0(pNode)) );
1719 break;
1720 }
1721 if ( fAcyclic )
1722 {
1723 Abc_NtkForEachLatchInput( pNtk, pNode, i )
1724 {
1725 pNode = Abc_ObjFanin0Ntk(Abc_ObjFanin0(pNode));
1726 if ( Abc_ObjIsBo(pNode) )
1727 pNode = Abc_ObjFanin0(pNode);
1728 if ( Abc_NodeIsTravIdPrevious(pNode) )
1729 continue;
1730 // traverse the output logic cone
1731 if ( (fAcyclic = Abc_NtkIsAcyclicWithBoxes_rec(pNode)) )
1732 continue;
1733 // stop as soon as the first loop is detected
1734 fprintf( stdout, " PO \"%s\"\n", Abc_ObjName(Abc_ObjFanout0(pNode)) );
1735 break;
1736 }
1737 }
1738 return fAcyclic;
1739 }
1740
1741
1742
1743 /**Function*************************************************************
1744
1745 Synopsis [Analyses choice nodes.]
1746
1747 Description []
1748
1749 SideEffects []
1750
1751 SeeAlso []
1752
1753 ***********************************************************************/
Abc_NodeSetChoiceLevel_rec(Abc_Obj_t * pNode,int fMaximum)1754 int Abc_NodeSetChoiceLevel_rec( Abc_Obj_t * pNode, int fMaximum )
1755 {
1756 Abc_Obj_t * pTemp;
1757 int Level1, Level2, Level, LevelE;
1758 // skip the visited node
1759 if ( Abc_NodeIsTravIdCurrent( pNode ) )
1760 return (int)(ABC_PTRINT_T)pNode->pCopy;
1761 Abc_NodeSetTravIdCurrent( pNode );
1762 // compute levels of the children nodes
1763 Level1 = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin0(pNode), fMaximum );
1764 Level2 = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin1(pNode), fMaximum );
1765 Level = 1 + Abc_MaxInt( Level1, Level2 );
1766 if ( pNode->pData )
1767 {
1768 LevelE = Abc_NodeSetChoiceLevel_rec( (Abc_Obj_t *)pNode->pData, fMaximum );
1769 if ( fMaximum )
1770 Level = Abc_MaxInt( Level, LevelE );
1771 else
1772 Level = Abc_MinInt( Level, LevelE );
1773 // set the level of all equivalent nodes to be the same minimum
1774 for ( pTemp = (Abc_Obj_t *)pNode->pData; pTemp; pTemp = (Abc_Obj_t *)pTemp->pData )
1775 pTemp->pCopy = (Abc_Obj_t *)(ABC_PTRINT_T)Level;
1776 }
1777 pNode->pCopy = (Abc_Obj_t *)(ABC_PTRINT_T)Level;
1778 return Level;
1779 }
1780
1781 /**Function*************************************************************
1782
1783 Synopsis [Resets the levels of the nodes in the choice graph.]
1784
1785 Description [Makes the level of the choice nodes to be equal to the
1786 maximum of the level of the nodes in the equivalence class. This way
1787 sorting by level leads to the reverse topological order, which is
1788 needed for the required time computation.]
1789
1790 SideEffects []
1791
1792 SeeAlso []
1793
1794 ***********************************************************************/
Abc_AigSetChoiceLevels(Abc_Ntk_t * pNtk)1795 int Abc_AigSetChoiceLevels( Abc_Ntk_t * pNtk )
1796 {
1797 Abc_Obj_t * pObj;
1798 int i, LevelMax, LevelCur;
1799 assert( Abc_NtkIsStrash(pNtk) );
1800 // set the new travid counter
1801 Abc_NtkIncrementTravId( pNtk );
1802 // set levels of the CI and constant
1803 Abc_NtkForEachCi( pNtk, pObj, i )
1804 {
1805 Abc_NodeSetTravIdCurrent( pObj );
1806 pObj->pCopy = NULL;
1807 }
1808 pObj = Abc_AigConst1( pNtk );
1809 Abc_NodeSetTravIdCurrent( pObj );
1810 pObj->pCopy = NULL;
1811 // set levels of all other nodes
1812 LevelMax = 0;
1813 Abc_NtkForEachCo( pNtk, pObj, i )
1814 {
1815 LevelCur = Abc_NodeSetChoiceLevel_rec( Abc_ObjFanin0(pObj), 1 );
1816 LevelMax = Abc_MaxInt( LevelMax, LevelCur );
1817 }
1818 return LevelMax;
1819 }
1820
1821 /**Function*************************************************************
1822
1823 Synopsis [Returns nodes by level from the smallest to the largest.]
1824
1825 Description [Correctly handles the case of choice nodes, by first
1826 spreading them out across several levels and then collecting.]
1827
1828 SideEffects [What happens with dangling nodes???]
1829
1830 SeeAlso []
1831
1832 ***********************************************************************/
Abc_AigGetLevelizedOrder(Abc_Ntk_t * pNtk,int fCollectCis)1833 Vec_Ptr_t * Abc_AigGetLevelizedOrder( Abc_Ntk_t * pNtk, int fCollectCis )
1834 {
1835 Vec_Ptr_t * vNodes, * vLevels;
1836 Abc_Obj_t * pNode, ** ppHead;
1837 int LevelMax, i;
1838 assert( Abc_NtkIsStrash(pNtk) );
1839 // set the correct levels
1840 Abc_NtkCleanCopy( pNtk );
1841 LevelMax = Abc_AigSetChoiceLevels( pNtk );
1842 // relink nodes by level
1843 vLevels = Vec_PtrStart( LevelMax + 1 );
1844 Abc_NtkForEachNode( pNtk, pNode, i )
1845 {
1846 ppHead = ((Abc_Obj_t **)vLevels->pArray) + (int)(ABC_PTRINT_T)pNode->pCopy;
1847 pNode->pCopy = *ppHead;
1848 *ppHead = pNode;
1849 }
1850 // recollect nodes
1851 vNodes = Vec_PtrStart( Abc_NtkNodeNum(pNtk) );
1852 Vec_PtrForEachEntryStart( Abc_Obj_t *, vLevels, pNode, i, !fCollectCis )
1853 for ( ; pNode; pNode = pNode->pCopy )
1854 Vec_PtrPush( vNodes, pNode );
1855 Vec_PtrFree( vLevels );
1856 return vNodes;
1857 }
1858
1859 /**Function*************************************************************
1860
1861 Synopsis [Count the number of nodes in the subgraph.]
1862
1863 Description []
1864
1865 SideEffects []
1866
1867 SeeAlso []
1868
1869 ***********************************************************************/
Abc_ObjSugraphSize(Abc_Obj_t * pObj)1870 int Abc_ObjSugraphSize( Abc_Obj_t * pObj )
1871 {
1872 if ( Abc_ObjIsCi(pObj) )
1873 return 0;
1874 if ( Abc_ObjFanoutNum(pObj) > 1 )
1875 return 0;
1876 return 1 + Abc_ObjSugraphSize(Abc_ObjFanin0(pObj)) +
1877 Abc_ObjSugraphSize(Abc_ObjFanin1(pObj));
1878 }
1879
1880 /**Function*************************************************************
1881
1882 Synopsis [Prints subgraphs.]
1883
1884 Description []
1885
1886 SideEffects []
1887
1888 SeeAlso []
1889
1890 ***********************************************************************/
Abc_NtkPrintSubraphSizes(Abc_Ntk_t * pNtk)1891 int Abc_NtkPrintSubraphSizes( Abc_Ntk_t * pNtk )
1892 {
1893 Abc_Obj_t * pObj;
1894 int i;
1895 assert( Abc_NtkIsStrash(pNtk) );
1896 Abc_NtkForEachNode( pNtk, pObj, i )
1897 if ( Abc_ObjFanoutNum(pObj) > 1 && !Abc_NodeIsExorType(pObj) )
1898 printf( "%d(%d) ", 1 + Abc_ObjSugraphSize(Abc_ObjFanin0(pObj)) +
1899 Abc_ObjSugraphSize(Abc_ObjFanin1(pObj)), Abc_ObjFanoutNum(pObj) );
1900 printf( "\n" );
1901 return 1;
1902 }
1903
1904 ////////////////////////////////////////////////////////////////////////
1905 /// END OF FILE ///
1906 ////////////////////////////////////////////////////////////////////////
1907
1908
1909 ABC_NAMESPACE_IMPL_END
1910
1911