abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
abcBalance.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [abcBalance.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Network and node package.]
8 
9  Synopsis [Performs global balancing of the AIG by the number of levels.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: abcBalance.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "base/abc/abc.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 static void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, int fDuplicate, int fSelective, int fUpdateLevel );
31 static Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int Level, int fDuplicate, int fSelective, int fUpdateLevel );
32 static Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vSuper, int Level, int fDuplicate, int fSelective );
33 static int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, int fFirst, int fDuplicate, int fSelective );
34 static void Abc_NtkMarkCriticalNodes( Abc_Ntk_t * pNtk );
35 static Vec_Ptr_t * Abc_NodeBalanceConeExor( Abc_Obj_t * pNode );
36 
37 
38 ////////////////////////////////////////////////////////////////////////
39 /// FUNCTION DEFINITIONS ///
40 ////////////////////////////////////////////////////////////////////////
41 
42 /**Function*************************************************************
43 
44  Synopsis [Balances the AIG network.]
45 
46  Description []
47 
48  SideEffects []
49 
50  SeeAlso []
51 
52 ***********************************************************************/
53 Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, int fDuplicate, int fSelective, int fUpdateLevel )
54 {
55 // extern void Abc_NtkHaigTranfer( Abc_Ntk_t * pNtkOld, Abc_Ntk_t * pNtkNew );
56  Abc_Ntk_t * pNtkAig;
57  assert( Abc_NtkIsStrash(pNtk) );
58  // compute the required times
59  if ( fSelective )
60  {
61  Abc_NtkStartReverseLevels( pNtk, 0 );
62  Abc_NtkMarkCriticalNodes( pNtk );
63  }
64  // perform balancing
65  pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
66  // transfer HAIG
67 // Abc_NtkHaigTranfer( pNtk, pNtkAig );
68  // perform balancing
69  Abc_NtkBalancePerform( pNtk, pNtkAig, fDuplicate, fSelective, fUpdateLevel );
70  Abc_NtkFinalize( pNtk, pNtkAig );
71  Abc_AigCleanup( (Abc_Aig_t *)pNtkAig->pManFunc );
72  // undo the required times
73  if ( fSelective )
74  {
75  Abc_NtkStopReverseLevels( pNtk );
76  Abc_NtkCleanMarkA( pNtk );
77  }
78  if ( pNtk->pExdc )
79  pNtkAig->pExdc = Abc_NtkDup( pNtk->pExdc );
80  // make sure everything is okay
81  if ( !Abc_NtkCheck( pNtkAig ) )
82  {
83  printf( "Abc_NtkBalance: The network check has failed.\n" );
84  Abc_NtkDelete( pNtkAig );
85  return NULL;
86  }
87 //Abc_NtkPrintCiLevels( pNtkAig );
88  return pNtkAig;
89 }
90 
91 /**Function*************************************************************
92 
93  Synopsis [Balances the AIG network.]
94 
95  Description []
96 
97  SideEffects []
98 
99  SeeAlso []
100 
101 ***********************************************************************/
102 void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, int fDuplicate, int fSelective, int fUpdateLevel )
103 {
104  ProgressBar * pProgress;
105  Vec_Vec_t * vStorage;
106  Abc_Obj_t * pNode;
107  int i;
108  // transfer level
109  Abc_NtkForEachCi( pNtk, pNode, i )
110  pNode->pCopy->Level = pNode->Level;
111  // set the level of PIs of AIG according to the arrival times of the old network
112  Abc_NtkSetNodeLevelsArrival( pNtk );
113  // allocate temporary storage for supergates
114  vStorage = Vec_VecStart( 10 );
115  // perform balancing of POs
116  pProgress = Extra_ProgressBarStart( stdout, Abc_NtkCoNum(pNtk) );
117  if ( pNtk->nBarBufs == 0 )
118  {
119  Abc_NtkForEachCo( pNtk, pNode, i )
120  {
121  Extra_ProgressBarUpdate( pProgress, i, NULL );
122  Abc_NodeBalance_rec( pNtkAig, Abc_ObjFanin0(pNode), vStorage, 0, fDuplicate, fSelective, fUpdateLevel );
123  }
124  }
125  else
126  {
127  Abc_NtkForEachLiPo( pNtk, pNode, i )
128  {
129  Extra_ProgressBarUpdate( pProgress, i, NULL );
130  Abc_NodeBalance_rec( pNtkAig, Abc_ObjFanin0(pNode), vStorage, 0, fDuplicate, fSelective, fUpdateLevel );
131  if ( i < pNtk->nBarBufs )
132  Abc_ObjFanout0(Abc_ObjFanout0(pNode))->Level = Abc_ObjFanin0(pNode)->Level;
133  }
134  }
135  Extra_ProgressBarStop( pProgress );
136  Vec_VecFree( vStorage );
137 }
138 
139 /**Function*************************************************************
140 
141  Synopsis [Finds the left bound on the next candidate to be paired.]
142 
143  Description [The nodes in the array are in the decreasing order of levels.
144  The last node in the array has the smallest level. By default it would be paired
145  with the next node on the left. However, it may be possible to pair it with some
146  other node on the left, in such a way that the new node is shared. This procedure
147  finds the index of the left-most node, which can be paired with the last node.]
148 
149  SideEffects []
150 
151  SeeAlso []
152 
153 ***********************************************************************/
154 int Abc_NodeBalanceFindLeft( Vec_Ptr_t * vSuper )
155 {
156  Abc_Obj_t * pNodeRight, * pNodeLeft;
157  int Current;
158  // if two or less nodes, pair with the first
159  if ( Vec_PtrSize(vSuper) < 3 )
160  return 0;
161  // set the pointer to the one before the last
162  Current = Vec_PtrSize(vSuper) - 2;
163  pNodeRight = (Abc_Obj_t *)Vec_PtrEntry( vSuper, Current );
164  // go through the nodes to the left of this one
165  for ( Current--; Current >= 0; Current-- )
166  {
167  // get the next node on the left
168  pNodeLeft = (Abc_Obj_t *)Vec_PtrEntry( vSuper, Current );
169  // if the level of this node is different, quit the loop
170  if ( Abc_ObjRegular(pNodeLeft)->Level != Abc_ObjRegular(pNodeRight)->Level )
171  break;
172  }
173  Current++;
174  // get the node, for which the equality holds
175  pNodeLeft = (Abc_Obj_t *)Vec_PtrEntry( vSuper, Current );
176  assert( Abc_ObjRegular(pNodeLeft)->Level == Abc_ObjRegular(pNodeRight)->Level );
177  return Current;
178 }
179 
180 /**Function*************************************************************
181 
182  Synopsis [Moves closer to the end the node that is best for sharing.]
183 
184  Description [If there is no node with sharing, randomly chooses one of
185  the legal nodes.]
186 
187  SideEffects []
188 
189  SeeAlso []
190 
191 ***********************************************************************/
192 void Abc_NodeBalancePermute( Abc_Ntk_t * pNtkNew, Vec_Ptr_t * vSuper, int LeftBound )
193 {
194  Abc_Obj_t * pNode1, * pNode2, * pNode3;
195  int RightBound, i;
196  // get the right bound
197  RightBound = Vec_PtrSize(vSuper) - 2;
198  assert( LeftBound <= RightBound );
199  if ( LeftBound == RightBound )
200  return;
201  // get the two last nodes
202  pNode1 = (Abc_Obj_t *)Vec_PtrEntry( vSuper, RightBound + 1 );
203  pNode2 = (Abc_Obj_t *)Vec_PtrEntry( vSuper, RightBound );
204  // find the first node that can be shared
205  for ( i = RightBound; i >= LeftBound; i-- )
206  {
207  pNode3 = (Abc_Obj_t *)Vec_PtrEntry( vSuper, i );
208  if ( Abc_AigAndLookup( (Abc_Aig_t *)pNtkNew->pManFunc, pNode1, pNode3 ) )
209  {
210  if ( pNode3 == pNode2 )
211  return;
212  Vec_PtrWriteEntry( vSuper, i, pNode2 );
213  Vec_PtrWriteEntry( vSuper, RightBound, pNode3 );
214  return;
215  }
216  }
217 /*
218  // we did not find the node to share, randomize choice
219  {
220  int Choice = rand() % (RightBound - LeftBound + 1);
221  pNode3 = Vec_PtrEntry( vSuper, LeftBound + Choice );
222  if ( pNode3 == pNode2 )
223  return;
224  Vec_PtrWriteEntry( vSuper, LeftBound + Choice, pNode2 );
225  Vec_PtrWriteEntry( vSuper, RightBound, pNode3 );
226  }
227 */
228 }
229 
230 /**Function*************************************************************
231 
232  Synopsis [Rebalances the multi-input node rooted at pNodeOld.]
233 
234  Description []
235 
236  SideEffects []
237 
238  SeeAlso []
239 
240 ***********************************************************************/
241 Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, Vec_Vec_t * vStorage, int Level, int fDuplicate, int fSelective, int fUpdateLevel )
242 {
243  Abc_Aig_t * pMan = (Abc_Aig_t *)pNtkNew->pManFunc;
244  Abc_Obj_t * pNodeNew, * pNode1, * pNode2;
245  Vec_Ptr_t * vSuper;
246  int i, LeftBound;
247  assert( !Abc_ObjIsComplement(pNodeOld) );
248  // return if the result if known
249  if ( pNodeOld->pCopy )
250  return pNodeOld->pCopy;
251  assert( Abc_ObjIsNode(pNodeOld) );
252  // get the implication supergate
253 // Abc_NodeBalanceConeExor( pNodeOld );
254  vSuper = Abc_NodeBalanceCone( pNodeOld, vStorage, Level, fDuplicate, fSelective );
255  if ( vSuper->nSize == 0 )
256  { // it means that the supergate contains two nodes in the opposite polarity
257  pNodeOld->pCopy = Abc_ObjNot(Abc_AigConst1(pNtkNew));
258  return pNodeOld->pCopy;
259  }
260  // for each old node, derive the new well-balanced node
261  for ( i = 0; i < vSuper->nSize; i++ )
262  {
263  pNodeNew = Abc_NodeBalance_rec( pNtkNew, Abc_ObjRegular((Abc_Obj_t *)vSuper->pArray[i]), vStorage, Level + 1, fDuplicate, fSelective, fUpdateLevel );
264  vSuper->pArray[i] = Abc_ObjNotCond( pNodeNew, Abc_ObjIsComplement((Abc_Obj_t *)vSuper->pArray[i]) );
265  }
266  if ( vSuper->nSize < 2 )
267  printf( "BUG!\n" );
268  // sort the new nodes by level in the decreasing order
269  Vec_PtrSort( vSuper, (int (*)(void))Abc_NodeCompareLevelsDecrease );
270  // balance the nodes
271  assert( vSuper->nSize > 1 );
272  while ( vSuper->nSize > 1 )
273  {
274  // find the left bound on the node to be paired
275  LeftBound = (!fUpdateLevel)? 0 : Abc_NodeBalanceFindLeft( vSuper );
276  // find the node that can be shared (if no such node, randomize choice)
277  Abc_NodeBalancePermute( pNtkNew, vSuper, LeftBound );
278  // pull out the last two nodes
279  pNode1 = (Abc_Obj_t *)Vec_PtrPop(vSuper);
280  pNode2 = (Abc_Obj_t *)Vec_PtrPop(vSuper);
281  Abc_VecObjPushUniqueOrderByLevel( vSuper, Abc_AigAnd(pMan, pNode1, pNode2) );
282  }
283  // make sure the balanced node is not assigned
284  assert( pNodeOld->pCopy == NULL );
285  // mark the old node with the new node
286  pNodeOld->pCopy = (Abc_Obj_t *)vSuper->pArray[0];
287  vSuper->nSize = 0;
288 // if ( Abc_ObjRegular(pNodeOld->pCopy) == Abc_AigConst1(pNtkNew) )
289 // printf( "Constant node\n" );
290 // assert( pNodeOld->Level >= Abc_ObjRegular(pNodeOld->pCopy)->Level );
291  return pNodeOld->pCopy;
292 }
293 
294 /**Function*************************************************************
295 
296  Synopsis [Collects the nodes in the cone delimited by fMarkA==1.]
297 
298  Description [Returns -1 if the AND-cone has the same node in both polarities.
299  Returns 1 if the AND-cone has the same node in the same polarity. Returns 0
300  if the AND-cone has no repeated nodes.]
301 
302  SideEffects []
303 
304  SeeAlso []
305 
306 ***********************************************************************/
307 Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int Level, int fDuplicate, int fSelective )
308 {
309  Vec_Ptr_t * vNodes;
310  int RetValue, i;
311  assert( !Abc_ObjIsComplement(pNode) );
312  // extend the storage
313  if ( Vec_VecSize( vStorage ) <= Level )
314  Vec_VecPush( vStorage, Level, 0 );
315  // get the temporary array of nodes
316  vNodes = Vec_VecEntry( vStorage, Level );
317  Vec_PtrClear( vNodes );
318  // collect the nodes in the implication supergate
319  RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, fDuplicate, fSelective );
320  assert( vNodes->nSize > 1 );
321  // unmark the visited nodes
322  for ( i = 0; i < vNodes->nSize; i++ )
323  Abc_ObjRegular((Abc_Obj_t *)vNodes->pArray[i])->fMarkB = 0;
324  // if we found the node and its complement in the same implication supergate,
325  // return empty set of nodes (meaning that we should use constant-0 node)
326  if ( RetValue == -1 )
327  vNodes->nSize = 0;
328  return vNodes;
329 }
330 
331 
332 /**Function*************************************************************
333 
334  Synopsis [Collects the nodes in the cone delimited by fMarkA==1.]
335 
336  Description [Returns -1 if the AND-cone has the same node in both polarities.
337  Returns 1 if the AND-cone has the same node in the same polarity. Returns 0
338  if the AND-cone has no repeated nodes.]
339 
340  SideEffects []
341 
342  SeeAlso []
343 
344 ***********************************************************************/
345 int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, int fFirst, int fDuplicate, int fSelective )
346 {
347  int RetValue1, RetValue2, i;
348  // check if the node is visited
349  if ( Abc_ObjRegular(pNode)->fMarkB )
350  {
351  // check if the node occurs in the same polarity
352  for ( i = 0; i < vSuper->nSize; i++ )
353  if ( vSuper->pArray[i] == pNode )
354  return 1;
355  // check if the node is present in the opposite polarity
356  for ( i = 0; i < vSuper->nSize; i++ )
357  if ( vSuper->pArray[i] == Abc_ObjNot(pNode) )
358  return -1;
359  assert( 0 );
360  return 0;
361  }
362  // if the new node is complemented or a PI, another gate begins
363  if ( !fFirst && (Abc_ObjIsComplement(pNode) || !Abc_ObjIsNode(pNode) || (!fDuplicate && !fSelective && (Abc_ObjFanoutNum(pNode) > 1)) || Vec_PtrSize(vSuper) > 10000) )
364  {
365  Vec_PtrPush( vSuper, pNode );
366  Abc_ObjRegular(pNode)->fMarkB = 1;
367  return 0;
368  }
369  assert( !Abc_ObjIsComplement(pNode) );
370  assert( Abc_ObjIsNode(pNode) );
371  // go through the branches
372  RetValue1 = Abc_NodeBalanceCone_rec( Abc_ObjChild0(pNode), vSuper, 0, fDuplicate, fSelective );
373  RetValue2 = Abc_NodeBalanceCone_rec( Abc_ObjChild1(pNode), vSuper, 0, fDuplicate, fSelective );
374  if ( RetValue1 == -1 || RetValue2 == -1 )
375  return -1;
376  // return 1 if at least one branch has a duplicate
377  return RetValue1 || RetValue2;
378 }
379 
380 
381 /**Function*************************************************************
382 
383  Synopsis []
384 
385  Description []
386 
387  SideEffects []
388 
389  SeeAlso []
390 
391 ***********************************************************************/
392 int Abc_NodeBalanceConeExor_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, int fFirst )
393 {
394  int RetValue1, RetValue2, i;
395  // check if the node occurs in the same polarity
396  for ( i = 0; i < vSuper->nSize; i++ )
397  if ( vSuper->pArray[i] == pNode )
398  return 1;
399  // if the new node is complemented or a PI, another gate begins
400  if ( !fFirst && (!pNode->fExor || !Abc_ObjIsNode(pNode)) )
401  {
402  Vec_PtrPush( vSuper, pNode );
403  return 0;
404  }
405  assert( !Abc_ObjIsComplement(pNode) );
406  assert( Abc_ObjIsNode(pNode) );
407  assert( pNode->fExor );
408  // go through the branches
409  RetValue1 = Abc_NodeBalanceConeExor_rec( Abc_ObjFanin0(Abc_ObjFanin0(pNode)), vSuper, 0 );
410  RetValue2 = Abc_NodeBalanceConeExor_rec( Abc_ObjFanin1(Abc_ObjFanin0(pNode)), vSuper, 0 );
411  if ( RetValue1 == -1 || RetValue2 == -1 )
412  return -1;
413  // return 1 if at least one branch has a duplicate
414  return RetValue1 || RetValue2;
415 }
416 
417 /**Function*************************************************************
418 
419  Synopsis []
420 
421  Description []
422 
423  SideEffects []
424 
425  SeeAlso []
426 
427 ***********************************************************************/
428 Vec_Ptr_t * Abc_NodeBalanceConeExor( Abc_Obj_t * pNode )
429 {
430  Vec_Ptr_t * vSuper;
431  if ( !pNode->fExor )
432  return NULL;
433  vSuper = Vec_PtrAlloc( 10 );
434  Abc_NodeBalanceConeExor_rec( pNode, vSuper, 1 );
435  printf( "%d ", Vec_PtrSize(vSuper) );
436  Vec_PtrFree( vSuper );
437  return NULL;
438 }
439 
440 
441 
442 /**Function*************************************************************
443 
444  Synopsis [Collects the nodes in the implication supergate.]
445 
446  Description []
447 
448  SideEffects []
449 
450  SeeAlso []
451 
452 ***********************************************************************/
453 Vec_Ptr_t * Abc_NodeFindCone_rec( Abc_Obj_t * pNode )
454 {
455  Vec_Ptr_t * vNodes;
456  Abc_Obj_t * pNodeC, * pNodeT, * pNodeE;
457  int RetValue, i;
458  assert( !Abc_ObjIsComplement(pNode) );
459  if ( Abc_ObjIsCi(pNode) )
460  return NULL;
461  // start the new array
462  vNodes = Vec_PtrAlloc( 4 );
463  // if the node is the MUX collect its fanins
464  if ( Abc_NodeIsMuxType(pNode) )
465  {
466  pNodeC = Abc_NodeRecognizeMux( pNode, &pNodeT, &pNodeE );
467  Vec_PtrPush( vNodes, Abc_ObjRegular(pNodeC) );
468  Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeT) );
469  Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeE) );
470  }
471  else
472  {
473  // collect the nodes in the implication supergate
474  RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, 1, 0 );
475  assert( vNodes->nSize > 1 );
476  // unmark the visited nodes
477  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
478  Abc_ObjRegular(pNode)->fMarkB = 0;
479  // if we found the node and its complement in the same implication supergate,
480  // return empty set of nodes (meaning that we should use constant-0 node)
481  if ( RetValue == -1 )
482  vNodes->nSize = 0;
483  }
484  // call for the fanin
485  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
486  {
487  pNode = Abc_ObjRegular(pNode);
488  if ( pNode->pCopy )
489  continue;
490  pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode );
491  }
492  return vNodes;
493 }
494 
495 /**Function*************************************************************
496 
497  Synopsis [Attaches the implication supergates to internal nodes.]
498 
499  Description []
500 
501  SideEffects []
502 
503  SeeAlso []
504 
505 ***********************************************************************/
506 void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk )
507 {
508  Abc_Obj_t * pNode;
509  int i;
510  Abc_NtkCleanCopy( pNtk );
511  Abc_NtkForEachCo( pNtk, pNode, i )
512  {
513  pNode = Abc_ObjFanin0(pNode);
514  if ( pNode->pCopy )
515  continue;
516  pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode );
517  }
518 }
519 
520 /**Function*************************************************************
521 
522  Synopsis [Attaches the implication supergates to internal nodes.]
523 
524  Description []
525 
526  SideEffects []
527 
528  SeeAlso []
529 
530 ***********************************************************************/
531 void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk )
532 {
533  Abc_Obj_t * pNode;
534  int i;
535  Abc_NtkForEachNode( pNtk, pNode, i )
536  if ( pNode->pCopy )
537  {
538  Vec_PtrFree( (Vec_Ptr_t *)pNode->pCopy );
539  pNode->pCopy = NULL;
540  }
541 }
542 
543 /**Function*************************************************************
544 
545  Synopsis [Compute levels of implication supergates.]
546 
547  Description []
548 
549  SideEffects []
550 
551  SeeAlso []
552 
553 ***********************************************************************/
554 int Abc_NtkBalanceLevel_rec( Abc_Obj_t * pNode )
555 {
556  Vec_Ptr_t * vSuper;
557  Abc_Obj_t * pFanin;
558  int i, LevelMax;
559  assert( !Abc_ObjIsComplement(pNode) );
560  if ( pNode->Level > 0 )
561  return pNode->Level;
562  if ( Abc_ObjIsCi(pNode) )
563  return 0;
564  vSuper = (Vec_Ptr_t *)pNode->pCopy;
565  assert( vSuper != NULL );
566  LevelMax = 0;
567  Vec_PtrForEachEntry( Abc_Obj_t *, vSuper, pFanin, i )
568  {
569  pFanin = Abc_ObjRegular(pFanin);
570  Abc_NtkBalanceLevel_rec(pFanin);
571  if ( LevelMax < (int)pFanin->Level )
572  LevelMax = pFanin->Level;
573  }
574  pNode->Level = LevelMax + 1;
575  return pNode->Level;
576 }
577 
578 
579 /**Function*************************************************************
580 
581  Synopsis [Compute levels of implication supergates.]
582 
583  Description []
584 
585  SideEffects []
586 
587  SeeAlso []
588 
589 ***********************************************************************/
590 void Abc_NtkBalanceLevel( Abc_Ntk_t * pNtk )
591 {
592  Abc_Obj_t * pNode;
593  int i;
594  Abc_NtkForEachObj( pNtk, pNode, i )
595  pNode->Level = 0;
596  Abc_NtkForEachCo( pNtk, pNode, i )
597  Abc_NtkBalanceLevel_rec( Abc_ObjFanin0(pNode) );
598 }
599 
600 
601 /**Function*************************************************************
602 
603  Synopsis [Marks the nodes on the critical and near critical paths.]
604 
605  Description []
606 
607  SideEffects []
608 
609  SeeAlso []
610 
611 ***********************************************************************/
612 void Abc_NtkMarkCriticalNodes( Abc_Ntk_t * pNtk )
613 {
614  Abc_Obj_t * pNode;
615  int i, Counter = 0;
616  Abc_NtkForEachNode( pNtk, pNode, i )
617  if ( Abc_ObjRequiredLevel(pNode) - pNode->Level <= 1 )
618  pNode->fMarkA = 1, Counter++;
619  printf( "The number of nodes on the critical paths = %6d (%5.2f %%)\n", Counter, 100.0 * Counter / Abc_NtkNodeNum(pNtk) );
620 }
621 
622 
623 ////////////////////////////////////////////////////////////////////////
624 /// END OF FILE ///
625 ////////////////////////////////////////////////////////////////////////
626 
627 
628 ABC_NAMESPACE_IMPL_END
629 
Abc_NodeBalanceConeExor_rec
int Abc_NodeBalanceConeExor_rec(Abc_Obj_t *pNode, Vec_Ptr_t *vSuper, int fFirst)
Definition: abcBalance.c:392
Abc_NtkIsStrash
static int Abc_NtkIsStrash(Abc_Ntk_t *pNtk)
Definition: abc.h:251
Abc_NtkBalanceAttach
void Abc_NtkBalanceAttach(Abc_Ntk_t *pNtk)
Definition: abcBalance.c:506
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
Vec_VecPush
static void Vec_VecPush(Vec_Vec_t *p, int Level, void *Entry)
Definition: vecVec.h:456
Abc_AigAndLookup
ABC_DLL Abc_Obj_t * Abc_AigAndLookup(Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1)
Definition: abcAig.c:403
Abc_ObjIsCi
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
Abc_Obj_t_::fMarkA
unsigned fMarkA
Definition: abc.h:134
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_Ntk_t_::pExdc
Abc_Ntk_t * pExdc
Definition: abc.h:201
Vec_PtrPushUnique
static int Vec_PtrPushUnique(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:656
Abc_Ntk_t_
Definition: abc.h:153
Abc_ObjFanoutNum
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
Abc_NodeBalanceConeExor
static Vec_Ptr_t * Abc_NodeBalanceConeExor(Abc_Obj_t *pNode)
Definition: abcBalance.c:428
Abc_NtkBalanceLevel
void Abc_NtkBalanceLevel(Abc_Ntk_t *pNtk)
Definition: abcBalance.c:590
Vec_PtrSort
static void Vec_PtrSort(Vec_Ptr_t *p, int(*Vec_PtrSortCompare)()) ___unused
Definition: vecPtr.h:851
Abc_NtkDup
ABC_DLL Abc_Ntk_t * Abc_NtkDup(Abc_Ntk_t *pNtk)
Definition: abcNtk.c:419
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Abc_NtkForEachCo
#define Abc_NtkForEachCo(pNtk, pCo, i)
Definition: abc.h:519
Abc_NtkCheck
ABC_DLL int Abc_NtkCheck(Abc_Ntk_t *pNtk)
FUNCTION DEFINITIONS ///.
Definition: abcCheck.c:61
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Vec_VecFree
static void Vec_VecFree(Vec_Vec_t *p)
Definition: vecVec.h:347
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_NtkCoNum
static int Abc_NtkCoNum(Abc_Ntk_t *pNtk)
Definition: abc.h:288
Abc_Aig_t_
DECLARATIONS ///.
Definition: abcAig.c:52
Abc_NodeBalance_rec
static Abc_Obj_t * Abc_NodeBalance_rec(Abc_Ntk_t *pNtkNew, Abc_Obj_t *pNode, Vec_Vec_t *vStorage, int Level, int fDuplicate, int fSelective, int fUpdateLevel)
Definition: abcBalance.c:241
Abc_NtkBalancePerform
static ABC_NAMESPACE_IMPL_START void Abc_NtkBalancePerform(Abc_Ntk_t *pNtk, Abc_Ntk_t *pNtkAig, int fDuplicate, int fSelective, int fUpdateLevel)
DECLARATIONS ///.
Definition: abcBalance.c:102
Abc_NtkStopReverseLevels
ABC_DLL void Abc_NtkStopReverseLevels(Abc_Ntk_t *pNtk)
Definition: abcTiming.c:1190
Abc_NtkDelete
ABC_DLL void Abc_NtkDelete(Abc_Ntk_t *pNtk)
Definition: abcNtk.c:1233
Abc_Obj_t_::Level
unsigned Level
Definition: abc.h:142
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjChild0
static Abc_Obj_t * Abc_ObjChild0(Abc_Obj_t *pObj)
Definition: abc.h:383
Abc_Ntk_t_::pManFunc
void * pManFunc
Definition: abc.h:191
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_NodeFindCone_rec
Vec_Ptr_t * Abc_NodeFindCone_rec(Abc_Obj_t *pNode)
Definition: abcBalance.c:453
Abc_NtkNodeNum
static int Abc_NtkNodeNum(Abc_Ntk_t *pNtk)
Definition: abc.h:293
Abc_NodeBalanceFindLeft
int Abc_NodeBalanceFindLeft(Vec_Ptr_t *vSuper)
Definition: abcBalance.c:154
Abc_NtkCleanMarkA
ABC_DLL void Abc_NtkCleanMarkA(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:663
Abc_AigAnd
ABC_DLL Abc_Obj_t * Abc_AigAnd(Abc_Aig_t *pMan, Abc_Obj_t *p0, Abc_Obj_t *p1)
Definition: abcAig.c:700
ProgressBarStruct
DECLARATIONS ///.
Definition: extraUtilProgress.c:32
Abc_NtkStartFrom
ABC_DLL Abc_Ntk_t * Abc_NtkStartFrom(Abc_Ntk_t *pNtk, Abc_NtkType_t Type, Abc_NtkFunc_t Func)
Definition: abcNtk.c:106
Abc_Obj_t_::pCopy
Abc_Obj_t * pCopy
Definition: abc.h:148
Abc_NodeIsMuxType
ABC_DLL int Abc_NodeIsMuxType(Abc_Obj_t *pNode)
Definition: abcUtil.c:1301
Abc_ObjRequiredLevel
ABC_DLL int Abc_ObjRequiredLevel(Abc_Obj_t *pObj)
Definition: abcTiming.c:1102
Abc_AigCleanup
ABC_DLL int Abc_AigCleanup(Abc_Aig_t *pMan)
Definition: abcAig.c:194
Abc_NtkMarkCriticalNodes
static void Abc_NtkMarkCriticalNodes(Abc_Ntk_t *pNtk)
Definition: abcBalance.c:612
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Abc_NtkFinalize
ABC_DLL void Abc_NtkFinalize(Abc_Ntk_t *pNtk, Abc_Ntk_t *pNtkNew)
Definition: abcNtk.c:302
Abc_VecObjPushUniqueOrderByLevel
ABC_DLL void Abc_VecObjPushUniqueOrderByLevel(Vec_Ptr_t *p, Abc_Obj_t *pNode)
Definition: abcUtil.c:1228
Counter
static int Counter
Definition: extraBddMisc.c:1877
Vec_VecStart
static Vec_Vec_t * Vec_VecStart(int nSize)
Definition: vecVec.h:168
Abc_NtkStartReverseLevels
ABC_DLL void Abc_NtkStartReverseLevels(Abc_Ntk_t *pNtk, int nMaxLevelIncrease)
Definition: abcTiming.c:1162
Extra_ProgressBarStop
void Extra_ProgressBarStop(ProgressBar *p)
Definition: extraUtilProgress.c:118
Abc_NodeBalanceCone_rec
static int Abc_NodeBalanceCone_rec(Abc_Obj_t *pNode, Vec_Ptr_t *vSuper, int fFirst, int fDuplicate, int fSelective)
Definition: abcBalance.c:345
Vec_PtrWriteEntry
static void Vec_PtrWriteEntry(Vec_Ptr_t *p, int i, void *Entry)
Definition: vecPtr.h:396
Abc_NodeBalanceCone
static Vec_Ptr_t * Abc_NodeBalanceCone(Abc_Obj_t *pNode, Vec_Vec_t *vSuper, int Level, int fDuplicate, int fSelective)
Definition: abcBalance.c:307
Abc_NtkBalance
Abc_Ntk_t * Abc_NtkBalance(Abc_Ntk_t *pNtk, int fDuplicate, int fSelective, int fUpdateLevel)
FUNCTION DEFINITIONS ///.
Definition: abcBalance.c:53
Abc_NtkForEachNode
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
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_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_::fMarkB
unsigned fMarkB
Definition: abc.h:135
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_Ntk_t_::nBarBufs
int nBarBufs
Definition: abc.h:174
Abc_NodeCompareLevelsDecrease
ABC_DLL int Abc_NodeCompareLevelsDecrease(Abc_Obj_t **pp1, Abc_Obj_t **pp2)
Definition: abcUtil.c:1675
Extra_ProgressBarStart
ProgressBar * Extra_ProgressBarStart(FILE *pFile, int nItemsTotal)
FUNCTION DEFINITIONS ///.
Definition: extraUtilProgress.c:62
Vec_VecSize
static int Vec_VecSize(Vec_Vec_t *p)
Definition: vecVec.h:222
Abc_NtkSetNodeLevelsArrival
ABC_DLL void Abc_NtkSetNodeLevelsArrival(Abc_Ntk_t *pNtk)
Definition: abcTiming.c:591
Abc_NtkCleanCopy
ABC_DLL void Abc_NtkCleanCopy(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:507
Abc_ObjNotCond
static Abc_Obj_t * Abc_ObjNotCond(Abc_Obj_t *p, int c)
Definition: abc.h:325
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ProgressBarUpdate
static void Extra_ProgressBarUpdate(ProgressBar *p, int nItemsCur, char *pString)
Definition: extra.h:243
Vec_PtrClear
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
Abc_ObjNot
static Abc_Obj_t * Abc_ObjNot(Abc_Obj_t *p)
Definition: abc.h:324
Abc_NtkBalanceDetach
void Abc_NtkBalanceDetach(Abc_Ntk_t *pNtk)
Definition: abcBalance.c:531
Vec_VecEntry
static Vec_Ptr_t * Vec_VecEntry(Vec_Vec_t *p, int i)
Definition: vecVec.h:271
Abc_Obj_t_::fExor
unsigned fExor
Definition: abc.h:138
Abc_NodeBalancePermute
void Abc_NodeBalancePermute(Abc_Ntk_t *pNtkNew, Vec_Ptr_t *vSuper, int LeftBound)
Definition: abcBalance.c:192
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Abc_ObjIsComplement
static int Abc_ObjIsComplement(Abc_Obj_t *p)
Definition: abc.h:322
Abc_NtkForEachObj
#define Abc_NtkForEachObj(pNtk, pObj, i)
ITERATORS ///.
Definition: abc.h:446
Abc_ObjChild1
static Abc_Obj_t * Abc_ObjChild1(Abc_Obj_t *pObj)
Definition: abc.h:384
Abc_NtkBalanceLevel_rec
int Abc_NtkBalanceLevel_rec(Abc_Obj_t *pNode)
Definition: abcBalance.c:554
Abc_NodeRecognizeMux
ABC_DLL Abc_Obj_t * Abc_NodeRecognizeMux(Abc_Obj_t *pNode, Abc_Obj_t **ppNodeT, Abc_Obj_t **ppNodeE)
Definition: abcUtil.c:1389
Abc_ObjFanout0
static Abc_Obj_t * Abc_ObjFanout0(Abc_Obj_t *pObj)
Definition: abc.h:371
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223