Version abc80130_2

1 files changed, 401 insertions, 26 deletions

diff --git a/src/base/abci/abcBalance.c b/src/base/abci/abcBalance.c
index 40701e41..f9b3384e 100644
--- a/src/base/abci/abcBalance.c
+++ b/src/base/abci/abcBalance.c
@@ -24,13 +24,16 @@
 ///                        DECLARATIONS                              ///
 ////////////////////////////////////////////////////////////////////////
  
-static void        Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate );
-static Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, Vec_Vec_t * vStorage, bool fDuplicate );
-static Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vSuper, int fDuplicate );
-static int         Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate );
+static void        Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate, bool fSelective, bool fUpdateLevel );
+static Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int Level, bool fDuplicate, bool fSelective, bool fUpdateLevel );
+static Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vSuper, int Level, int fDuplicate, bool fSelective );
+static int         Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate, bool fSelective );
+static void        Abc_NtkMarkCriticalNodes( Abc_Ntk_t * pNtk );
+static Vec_Ptr_t * Abc_NodeBalanceConeExor( Abc_Obj_t * pNode );
+
 
 ////////////////////////////////////////////////////////////////////////
-///                     FUNCTION DEFITIONS                           ///
+///                     FUNCTION DEFINITIONS                         ///
 ////////////////////////////////////////////////////////////////////////
 
 /**Function*************************************************************
@@ -44,14 +47,32 @@ static int         Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSupe
   SeeAlso     []
 
 ***********************************************************************/
-Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, bool fDuplicate )
+Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, bool fDuplicate, bool fSelective, bool fUpdateLevel )
 {
+    extern void Abc_NtkHaigTranfer( Abc_Ntk_t * pNtkOld, Abc_Ntk_t * pNtkNew );
     Abc_Ntk_t * pNtkAig;
     assert( Abc_NtkIsStrash(pNtk) );
+    // compute the required times
+    if ( fSelective )
+    {
+        Abc_NtkStartReverseLevels( pNtk, 0 );
+        Abc_NtkMarkCriticalNodes( pNtk );
+    }
     // perform balancing
-    pNtkAig = Abc_NtkStartFrom( pNtk, ABC_TYPE_STRASH, ABC_FUNC_AIG );
-    Abc_NtkBalancePerform( pNtk, pNtkAig, fDuplicate );
+    pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
+    // transfer HAIG
+    Abc_NtkHaigTranfer( pNtk, pNtkAig );
+    // perform balancing
+    Abc_NtkBalancePerform( pNtk, pNtkAig, fDuplicate, fSelective, fUpdateLevel );
     Abc_NtkFinalize( pNtk, pNtkAig );
+    // undo the required times
+    if ( fSelective )
+    {
+        Abc_NtkStopReverseLevels( pNtk );
+        Abc_NtkCleanMarkA( pNtk );
+    }
+    if ( pNtk->pExdc )
+        pNtkAig->pExdc = Abc_NtkDup( pNtk->pExdc );
     // make sure everything is okay
     if ( !Abc_NtkCheck( pNtkAig ) )
     {
@@ -73,7 +94,7 @@ Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, bool fDuplicate )
   SeeAlso     []
 
 ***********************************************************************/
-void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate )
+void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplicate, bool fSelective, bool fUpdateLevel )
 {
     int fCheck = 1;
     ProgressBar * pProgress;
@@ -81,12 +102,10 @@ void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplica
     Abc_Obj_t * pNode, * pDriver;
     int i;
 
-    // copy the constant node
-    Abc_AigConst1(pNtk->pManFunc)->pCopy = Abc_AigConst1(pNtkAig->pManFunc);
     // set the level of PIs of AIG according to the arrival times of the old network
     Abc_NtkSetNodeLevelsArrival( pNtk );
     // allocate temporary storage for supergates
-    vStorage = Vec_VecStart( Abc_AigGetLevelNum(pNtk) + 1 );
+    vStorage = Vec_VecStart( 10 );
     // perform balancing of POs
     pProgress = Extra_ProgressBarStart( stdout, Abc_NtkCoNum(pNtk) );
     Abc_NtkForEachCo( pNtk, pNode, i )
@@ -94,7 +113,7 @@ void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplica
         Extra_ProgressBarUpdate( pProgress, i, NULL );
         // strash the driver node
         pDriver = Abc_ObjFanin0(pNode);
-        Abc_NodeBalance_rec( pNtkAig, pDriver, vStorage, fDuplicate );
+        Abc_NodeBalance_rec( pNtkAig, pDriver, vStorage, 0, fDuplicate, fSelective, fUpdateLevel );
     }
     Extra_ProgressBarStop( pProgress );
     Vec_VecFree( vStorage );
@@ -102,6 +121,97 @@ void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplica
 
 /**Function*************************************************************
 
+  Synopsis    [Finds the left bound on the next candidate to be paired.]
+
+  Description [The nodes in the array are in the decreasing order of levels. 
+  The last node in the array has the smallest level. By default it would be paired 
+  with the next node on the left. However, it may be possible to pair it with some
+  other node on the left, in such a way that the new node is shared. This procedure
+  finds the index of the left-most node, which can be paired with the last node.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NodeBalanceFindLeft( Vec_Ptr_t * vSuper )
+{
+    Abc_Obj_t * pNodeRight, * pNodeLeft;
+    int Current;
+    // if two or less nodes, pair with the first
+    if ( Vec_PtrSize(vSuper) < 3 )
+        return 0;
+    // set the pointer to the one before the last
+    Current = Vec_PtrSize(vSuper) - 2;
+    pNodeRight = Vec_PtrEntry( vSuper, Current );
+    // go through the nodes to the left of this one
+    for ( Current--; Current >= 0; Current-- )
+    {
+        // get the next node on the left
+        pNodeLeft = Vec_PtrEntry( vSuper, Current );
+        // if the level of this node is different, quit the loop
+        if ( Abc_ObjRegular(pNodeLeft)->Level != Abc_ObjRegular(pNodeRight)->Level )
+            break;
+    }
+    Current++;    
+    // get the node, for which the equality holds
+    pNodeLeft = Vec_PtrEntry( vSuper, Current );
+    assert( Abc_ObjRegular(pNodeLeft)->Level == Abc_ObjRegular(pNodeRight)->Level );
+    return Current;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Moves closer to the end the node that is best for sharing.]
+
+  Description [If there is no node with sharing, randomly chooses one of 
+  the legal nodes.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NodeBalancePermute( Abc_Ntk_t * pNtkNew, Vec_Ptr_t * vSuper, int LeftBound )
+{
+    Abc_Obj_t * pNode1, * pNode2, * pNode3;
+    int RightBound, i;
+    // get the right bound
+    RightBound = Vec_PtrSize(vSuper) - 2;
+    assert( LeftBound <= RightBound );
+    if ( LeftBound == RightBound )
+        return;
+    // get the two last nodes
+    pNode1 = Vec_PtrEntry( vSuper, RightBound + 1 );
+    pNode2 = Vec_PtrEntry( vSuper, RightBound     );
+    // find the first node that can be shared
+    for ( i = RightBound; i >= LeftBound; i-- )
+    {
+        pNode3 = Vec_PtrEntry( vSuper, i );
+        if ( Abc_AigAndLookup( pNtkNew->pManFunc, pNode1, pNode3 ) )
+        {
+            if ( pNode3 == pNode2 )
+                return;
+            Vec_PtrWriteEntry( vSuper, i,          pNode2 );
+            Vec_PtrWriteEntry( vSuper, RightBound, pNode3 );
+            return;
+        }
+    }
+/*
+    // we did not find the node to share, randomize choice
+    {
+        int Choice = rand() % (RightBound - LeftBound + 1);
+        pNode3 = Vec_PtrEntry( vSuper, LeftBound + Choice );
+        if ( pNode3 == pNode2 )
+            return;
+        Vec_PtrWriteEntry( vSuper, LeftBound + Choice, pNode2 );
+        Vec_PtrWriteEntry( vSuper, RightBound,         pNode3 );
+    }
+*/
+}
+
+/**Function*************************************************************
+
   Synopsis    [Rebalances the multi-input node rooted at pNodeOld.]
 
   Description []
@@ -111,36 +221,44 @@ void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, bool fDuplica
   SeeAlso     []
 
 ***********************************************************************/
-Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, Vec_Vec_t * vStorage, bool fDuplicate )
+Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, Vec_Vec_t * vStorage, int Level, bool fDuplicate, bool fSelective, bool fUpdateLevel )
 {
     Abc_Aig_t * pMan = pNtkNew->pManFunc;
     Abc_Obj_t * pNodeNew, * pNode1, * pNode2;
     Vec_Ptr_t * vSuper;
-    int i;
+    int i, LeftBound;
     assert( !Abc_ObjIsComplement(pNodeOld) );
     // return if the result if known
     if ( pNodeOld->pCopy )
         return pNodeOld->pCopy;
     assert( Abc_ObjIsNode(pNodeOld) );
     // get the implication supergate
-    vSuper = Abc_NodeBalanceCone( pNodeOld, vStorage, fDuplicate );
+//    Abc_NodeBalanceConeExor( pNodeOld );
+    vSuper = Abc_NodeBalanceCone( pNodeOld, vStorage, Level, fDuplicate, fSelective );
     if ( vSuper->nSize == 0 )
     { // it means that the supergate contains two nodes in the opposite polarity
-        pNodeOld->pCopy = Abc_ObjNot(Abc_AigConst1(pMan));
+        pNodeOld->pCopy = Abc_ObjNot(Abc_AigConst1(pNtkNew));
         return pNodeOld->pCopy;
     }
     // for each old node, derive the new well-balanced node
     for ( i = 0; i < vSuper->nSize; i++ )
     {
-        pNodeNew = Abc_NodeBalance_rec( pNtkNew, Abc_ObjRegular(vSuper->pArray[i]), vStorage, fDuplicate );
+        pNodeNew = Abc_NodeBalance_rec( pNtkNew, Abc_ObjRegular(vSuper->pArray[i]), vStorage, Level + 1, fDuplicate, fSelective, fUpdateLevel );
         vSuper->pArray[i] = Abc_ObjNotCond( pNodeNew, Abc_ObjIsComplement(vSuper->pArray[i]) );
     }
+    if ( vSuper->nSize < 2 )
+        printf( "BUG!\n" );
     // sort the new nodes by level in the decreasing order
     Vec_PtrSort( vSuper, Abc_NodeCompareLevelsDecrease );
     // balance the nodes
     assert( vSuper->nSize > 1 );
     while ( vSuper->nSize > 1 )
     {
+        // find the left bound on the node to be paired
+        LeftBound = (!fUpdateLevel)? 0 : Abc_NodeBalanceFindLeft( vSuper );
+        // find the node that can be shared (if no such node, randomize choice)
+        Abc_NodeBalancePermute( pNtkNew, vSuper, LeftBound );
+        // pull out the last two nodes
         pNode1 = Vec_PtrPop(vSuper);
         pNode2 = Vec_PtrPop(vSuper);
         Abc_VecObjPushUniqueOrderByLevel( vSuper, Abc_AigAnd(pMan, pNode1, pNode2) );
@@ -149,6 +267,13 @@ Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, Vec_
     assert( pNodeOld->pCopy == NULL );
     // mark the old node with the new node
     pNodeOld->pCopy = vSuper->pArray[0];
+    vSuper->nSize = 0;
+//    if ( Abc_ObjRegular(pNodeOld->pCopy) == Abc_AigConst1(pNtkNew) )
+//        printf( "Constant node\n" );
+//    assert( pNodeOld->Level >= Abc_ObjRegular(pNodeOld->pCopy)->Level );
+    // update HAIG
+    if ( Abc_ObjRegular(pNodeOld->pCopy)->pNtk->pHaig )
+        Hop_ObjCreateChoice( pNodeOld->pEquiv, Abc_ObjRegular(pNodeOld->pCopy)->pEquiv );
     return pNodeOld->pCopy;
 }
 
@@ -165,17 +290,25 @@ Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, Vec_
   SeeAlso     []
 
 ***********************************************************************/
-Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int fDuplicate )
+Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int Level, int fDuplicate, bool fSelective )
 {
     Vec_Ptr_t * vNodes;
     int RetValue, i;
     assert( !Abc_ObjIsComplement(pNode) );
-    vNodes = Vec_VecEntry( vStorage, pNode->Level );
+    // extend the storage
+    if ( Vec_VecSize( vStorage ) <= Level )
+        Vec_VecPush( vStorage, Level, 0 );
+    // get the temporary array of nodes
+    vNodes = Vec_VecEntry( vStorage, Level );
     Vec_PtrClear( vNodes );
-    RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, fDuplicate );
-    assert( vNodes->nSize > 0 );
+    // collect the nodes in the implication supergate
+    RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, fDuplicate, fSelective );
+    assert( vNodes->nSize > 1 );
+    // unmark the visited nodes
     for ( i = 0; i < vNodes->nSize; i++ )
         Abc_ObjRegular((Abc_Obj_t *)vNodes->pArray[i])->fMarkB = 0;
+    // if we found the node and its complement in the same implication supergate, 
+    // return empty set of nodes (meaning that we should use constant-0 node)
     if ( RetValue == -1 )
         vNodes->nSize = 0;
     return vNodes;
@@ -195,7 +328,7 @@ Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int fD
   SeeAlso     []
 
 ***********************************************************************/
-int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate )
+int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst, bool fDuplicate, bool fSelective )
 {
     int RetValue1, RetValue2, i;
     // check if the node is visited
@@ -213,7 +346,7 @@ int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst,
         return 0;
     }
     // if the new node is complemented or a PI, another gate begins
-    if ( !fFirst && (Abc_ObjIsComplement(pNode) || !Abc_ObjIsNode(pNode) || !fDuplicate && (Abc_ObjFanoutNum(pNode) > 1)) )
+    if ( !fFirst && (Abc_ObjIsComplement(pNode) || !Abc_ObjIsNode(pNode) || !fDuplicate && !fSelective && (Abc_ObjFanoutNum(pNode) > 1)) )
     {
         Vec_PtrPush( vSuper, pNode );
         Abc_ObjRegular(pNode)->fMarkB = 1;
@@ -222,8 +355,8 @@ int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst,
     assert( !Abc_ObjIsComplement(pNode) );
     assert( Abc_ObjIsNode(pNode) );
     // go through the branches
-    RetValue1 = Abc_NodeBalanceCone_rec( Abc_ObjChild0(pNode), vSuper, 0, fDuplicate );
-    RetValue2 = Abc_NodeBalanceCone_rec( Abc_ObjChild1(pNode), vSuper, 0, fDuplicate );
+    RetValue1 = Abc_NodeBalanceCone_rec( Abc_ObjChild0(pNode), vSuper, 0, fDuplicate, fSelective );
+    RetValue2 = Abc_NodeBalanceCone_rec( Abc_ObjChild1(pNode), vSuper, 0, fDuplicate, fSelective );
     if ( RetValue1 == -1 || RetValue2 == -1 )
         return -1;
     // return 1 if at least one branch has a duplicate
@@ -231,6 +364,248 @@ int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst,
 }
 
 
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NodeBalanceConeExor_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, bool fFirst )
+{
+    int RetValue1, RetValue2, i;
+    // check if the node occurs in the same polarity
+    for ( i = 0; i < vSuper->nSize; i++ )
+        if ( vSuper->pArray[i] == pNode )
+            return 1;
+    // if the new node is complemented or a PI, another gate begins
+    if ( !fFirst && (!pNode->fExor || !Abc_ObjIsNode(pNode)) )
+    {
+        Vec_PtrPush( vSuper, pNode );
+        return 0;
+    }
+    assert( !Abc_ObjIsComplement(pNode) );
+    assert( Abc_ObjIsNode(pNode) );
+    assert( pNode->fExor );
+    // go through the branches
+    RetValue1 = Abc_NodeBalanceConeExor_rec( Abc_ObjFanin0(Abc_ObjFanin0(pNode)), vSuper, 0 );
+    RetValue2 = Abc_NodeBalanceConeExor_rec( Abc_ObjFanin1(Abc_ObjFanin0(pNode)), vSuper, 0 );
+    if ( RetValue1 == -1 || RetValue2 == -1 )
+        return -1;
+    // return 1 if at least one branch has a duplicate
+    return RetValue1 || RetValue2;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Abc_NodeBalanceConeExor( Abc_Obj_t * pNode )
+{
+    Vec_Ptr_t * vSuper;
+    if ( !pNode->fExor )
+        return NULL;
+    vSuper = Vec_PtrAlloc( 10 );
+    Abc_NodeBalanceConeExor_rec( pNode, vSuper, 1 );
+    printf( "%d ", Vec_PtrSize(vSuper) );
+    Vec_PtrFree( vSuper );
+    return NULL;
+}
+
+
+
+/**Function*************************************************************
+
+  Synopsis    [Collects the nodes in the implication supergate.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Ptr_t * Abc_NodeFindCone_rec( Abc_Obj_t * pNode )
+{
+    Vec_Ptr_t * vNodes;
+    Abc_Obj_t * pNodeC, * pNodeT, * pNodeE;
+    int RetValue, i;
+    assert( !Abc_ObjIsComplement(pNode) );
+    if ( Abc_ObjIsCi(pNode) )
+        return NULL;
+    // start the new array
+    vNodes = Vec_PtrAlloc( 4 );
+    // if the node is the MUX collect its fanins
+    if ( Abc_NodeIsMuxType(pNode) )
+    {
+        pNodeC = Abc_NodeRecognizeMux( pNode, &pNodeT, &pNodeE );
+        Vec_PtrPush( vNodes, Abc_ObjRegular(pNodeC) );
+        Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeT) );
+        Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeE) );
+    }
+    else
+    {
+        // collect the nodes in the implication supergate
+        RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, 1, 0 );
+        assert( vNodes->nSize > 1 );
+        // unmark the visited nodes
+        Vec_PtrForEachEntry( vNodes, pNode, i )
+            Abc_ObjRegular(pNode)->fMarkB = 0;
+        // if we found the node and its complement in the same implication supergate, 
+        // return empty set of nodes (meaning that we should use constant-0 node)
+        if ( RetValue == -1 )
+            vNodes->nSize = 0;
+    }
+    // call for the fanin
+    Vec_PtrForEachEntry( vNodes, pNode, i )
+    {
+        pNode = Abc_ObjRegular(pNode);
+        if ( pNode->pCopy )
+            continue;
+        pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode );
+    }
+    return vNodes;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Attaches the implication supergates to internal nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk )
+{
+    Abc_Obj_t * pNode;
+    int i;
+    Abc_NtkCleanCopy( pNtk );
+    Abc_NtkForEachCo( pNtk, pNode, i )
+    {
+        pNode = Abc_ObjFanin0(pNode);
+        if ( pNode->pCopy )
+            continue;
+        pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode );
+    }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Attaches the implication supergates to internal nodes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk )
+{
+    Abc_Obj_t * pNode;
+    int i;
+    Abc_NtkForEachNode( pNtk, pNode, i )
+        if ( pNode->pCopy )
+        {
+            Vec_PtrFree( (Vec_Ptr_t *)pNode->pCopy );
+            pNode->pCopy = NULL;
+        }
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Compute levels of implication supergates.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NtkBalanceLevel_rec( Abc_Obj_t * pNode )
+{
+    Vec_Ptr_t * vSuper;
+    Abc_Obj_t * pFanin;
+    int i, LevelMax;
+    assert( !Abc_ObjIsComplement(pNode) );
+    if ( pNode->Level > 0 )
+        return pNode->Level;
+    if ( Abc_ObjIsCi(pNode) )
+        return 0;
+    vSuper = (Vec_Ptr_t *)pNode->pCopy;
+    assert( vSuper != NULL );
+    LevelMax = 0;
+    Vec_PtrForEachEntry( vSuper, pFanin, i )
+    {
+        pFanin = Abc_ObjRegular(pFanin);
+        Abc_NtkBalanceLevel_rec(pFanin);
+        if ( LevelMax < (int)pFanin->Level )
+            LevelMax = pFanin->Level;
+    }
+    pNode->Level = LevelMax + 1;
+    return pNode->Level;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Compute levels of implication supergates.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NtkBalanceLevel( Abc_Ntk_t * pNtk )
+{
+    Abc_Obj_t * pNode;
+    int i;
+    Abc_NtkForEachObj( pNtk, pNode, i )
+        pNode->Level = 0;
+    Abc_NtkForEachCo( pNtk, pNode, i )
+        Abc_NtkBalanceLevel_rec( Abc_ObjFanin0(pNode) );
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Marks the nodes on the critical and near critical paths.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_NtkMarkCriticalNodes( Abc_Ntk_t * pNtk )
+{
+    Abc_Obj_t * pNode;
+    int i, Counter = 0;
+    Abc_NtkForEachNode( pNtk, pNode, i )
+        if ( Abc_ObjRequiredLevel(pNode) - pNode->Level <= 1 )
+            pNode->fMarkA = 1, Counter++;
+    printf( "The number of nodes on the critical paths = %6d  (%5.2f %%)\n", Counter, 100.0 * Counter / Abc_NtkNodeNum(pNtk) );
+}
+
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////