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