Experiments with don't-cares.

1 files changed, 103 insertions, 147 deletions

diff --git a/src/base/acb/acbUtil.c b/src/base/acb/acbUtil.c
index ab9bf44c..cc8b9f11 100644
--- a/src/base/acb/acbUtil.c
+++ b/src/base/acb/acbUtil.c
@@ -33,38 +33,7 @@ ABC_NAMESPACE_IMPL_START
 
 /**Function*************************************************************
 
-  Synopsis    []
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-void Acb_ObjAddFanout( Acb_Ntk_t * p, int iObj )
-{
-    int k, iFanin, * pFanins; 
-    Acb_ObjForEachFaninFast( p, iObj, pFanins, iFanin, k )
-        Vec_IntPush( Vec_WecEntry(&p->vFanouts, iFanin), iObj );
-}
-void Acb_ObjRemoveFanout( Acb_Ntk_t * p, int iObj )
-{
-    int k, iFanin, * pFanins; 
-    Acb_ObjForEachFaninFast( p, iObj, pFanins, iFanin, k )
-        Vec_IntRemove( Vec_WecEntry(&p->vFanouts, iFanin), iObj );
-}
-void Acb_NtkCreateFanout( Acb_Ntk_t * p )
-{
-    int iObj; 
-    Vec_WecInit( &p->vFanouts, Acb_NtkObjNumMax(p) );
-    Acb_NtkForEachObj( p, iObj )
-        Acb_ObjAddFanout( p, iObj );
-}
-
-/**Function*************************************************************
-
-  Synopsis    []
+  Synopsis    [Collecting TFI and TFO.]
 
   Description []
                
@@ -86,9 +55,14 @@ void Acb_ObjCollectTfi_rec( Acb_Ntk_t * p, int iObj, int fTerm )
 }
 Vec_Int_t * Acb_ObjCollectTfi( Acb_Ntk_t * p, int iObj, int fTerm )
 {
+    int i;
     Vec_IntClear( &p->vArray0 );
     Acb_NtkIncTravId( p );
-    Acb_ObjCollectTfi_rec( p, iObj, fTerm );
+    if ( iObj > 0 )
+        Acb_ObjCollectTfi_rec( p, iObj, fTerm );
+    else
+        Acb_NtkForEachCo( p, iObj, i )
+            Acb_ObjCollectTfi_rec( p, iObj, fTerm );
     return &p->vArray0;
 }
 
@@ -105,16 +79,20 @@ void Acb_ObjCollectTfo_rec( Acb_Ntk_t * p, int iObj, int fTerm )
 }
 Vec_Int_t * Acb_ObjCollectTfo( Acb_Ntk_t * p, int iObj, int fTerm )
 {
+    int i;
     Vec_IntClear( &p->vArray1 );
     Acb_NtkIncTravId( p );
-    Acb_ObjCollectTfo_rec( p, iObj, fTerm );
+    if ( iObj > 0 )
+        Acb_ObjCollectTfo_rec( p, iObj, fTerm );
+    else
+        Acb_NtkForEachCi( p, iObj, i )
+            Acb_ObjCollectTfo_rec( p, iObj, fTerm );
     return &p->vArray1;
 }
 
-
 /**Function*************************************************************
 
-  Synopsis    []
+  Synopsis    [Computing and updating direct and reverse logic level.]
 
   Description []
                
@@ -132,19 +110,12 @@ int Acb_ObjComputeLevelD( Acb_Ntk_t * p, int iObj )
 }
 int Acb_NtkComputeLevelD( Acb_Ntk_t * p, Vec_Int_t * vTfo )
 {
+    // it is assumed that vTfo contains CO nodes and level of new nodes was already updated
     int i, iObj, Level = 0;
-    if ( vTfo == NULL )
-    {
+    if ( !Acb_NtkHasObjLevelD( p ) )
         Acb_NtkCleanObjLevelD( p );
-        Acb_NtkForEachObj( p, iObj )
-            Acb_ObjComputeLevelD( p, iObj );
-    }
-    else
-    {
-        // it is assumed that vTfo contains CO nodes and level of new nodes was already updated
-        Vec_IntForEachEntry( vTfo, iObj, i )
-            Acb_ObjComputeLevelD( p, iObj );
-    }
+    Vec_IntForEachEntryReverse( vTfo, iObj, i )
+        Acb_ObjComputeLevelD( p, iObj );
     Acb_NtkForEachCo( p, iObj, i )
         Level = Abc_MaxInt( Level, Acb_ObjLevelD(p, iObj) );
     p->LevelMax = Level;
@@ -160,28 +131,27 @@ int Acb_ObjComputeLevelR( Acb_Ntk_t * p, int iObj )
 }
 int Acb_NtkComputeLevelR( Acb_Ntk_t * p, Vec_Int_t * vTfi )
 {
+    // it is assumed that vTfi contains CI nodes
     int i, iObj, Level = 0;
-    if ( vTfi == NULL )
-    {
-        Acb_NtkCleanObjLevelR( p );
-        Acb_NtkForEachObjReverse( p, iObj )
-            Acb_ObjComputeLevelR( p, iObj );
-    }
-    else
-    {
-        // it is assumed that vTfi contains CI nodes
-        Vec_IntForEachEntryReverse( vTfi, iObj, i )
-            Acb_ObjComputeLevelR( p, iObj );
-    }
+    if ( !Acb_NtkHasObjLevelD( p ) )
+        Acb_NtkCleanObjLevelD( p );
+    Vec_IntForEachEntryReverse( vTfi, iObj, i )
+        Acb_ObjComputeLevelR( p, iObj );
     Acb_NtkForEachCi( p, iObj, i )
         Level = Abc_MaxInt( Level, Acb_ObjLevelR(p, iObj) );
     assert( p->LevelMax == Level );
     return Level;
 }
 
+void Acb_NtkUpdateLevelD( Acb_Ntk_t * p, int Pivot )
+{
+    Vec_Int_t * vTfo = Acb_ObjCollectTfo( p, Pivot, 1 );
+    Acb_NtkComputeLevelD( p, vTfo );
+}
+
 /**Function*************************************************************
 
-  Synopsis    []
+  Synopsis    [Computing and updating direct and reverse path count.]
 
   Description []
                
@@ -192,9 +162,11 @@ int Acb_NtkComputeLevelR( Acb_Ntk_t * p, Vec_Int_t * vTfi )
 ***********************************************************************/
 int Acb_ObjSlack( Acb_Ntk_t * p, int iObj )
 {
-    assert( !Acb_ObjIsCio(p, iObj) + p->LevelMax >= Acb_ObjLevelD(p, iObj) + Acb_ObjLevelR(p, iObj) );
-    return !Acb_ObjIsCio(p, iObj) + p->LevelMax - Acb_ObjLevelD(p, iObj) - Acb_ObjLevelR(p, iObj);
+    int LevelSum = Acb_ObjLevelD(p, iObj) + Acb_ObjLevelR(p, iObj);
+    assert( !Acb_ObjIsCio(p, iObj) + p->LevelMax >= LevelSum );
+    return !Acb_ObjIsCio(p, iObj) + p->LevelMax - LevelSum;
 }
+
 int Acb_ObjComputePathD( Acb_Ntk_t * p, int iObj )
 {
     int * pFanins, iFanin, k, Path = 0;
@@ -207,26 +179,13 @@ int Acb_ObjComputePathD( Acb_Ntk_t * p, int iObj )
 int Acb_NtkComputePathsD( Acb_Ntk_t * p, Vec_Int_t * vTfo )
 {
     int i, iObj, Path = 0;
-    if ( vTfo == NULL )
-    {
-        Acb_NtkCleanObjPathD( p );
-        Acb_NtkForEachCi( p, iObj, i )
-            if ( Acb_ObjLevelR(p, iObj) == p->LevelMax )
-                Acb_ObjSetPathD( p, iObj, 1 );
-        Acb_NtkForEachObj( p, iObj )
-            if ( !Acb_ObjIsCi(p, iObj) && !Acb_ObjSlack(p, iObj) )
-                Acb_ObjComputePathD( p, iObj );
-    }
-    else
-    {
-        // it is assumed that vTfo contains CO nodes
-        assert( Acb_ObjSlack(p, Vec_IntEntry(vTfo, 0)) );
-        Vec_IntForEachEntry( vTfo, iObj, i )
-            if ( !Acb_ObjSlack(p, iObj) )
-                Acb_ObjComputePathD( p, iObj );
-            else
-                Acb_ObjSetPathD( p, iObj, 0 );
-    }
+    // it is assumed that vTfo contains CO nodes
+    //assert( Acb_ObjSlack(p, Vec_IntEntry(vTfo, 0)) );
+    Vec_IntForEachEntryReverse( vTfo, iObj, i )
+        if ( !Acb_ObjSlack(p, iObj) )
+            Acb_ObjComputePathD( p, iObj );
+        else
+            Acb_ObjSetPathD( p, iObj, 0 );
     Acb_NtkForEachCo( p, iObj, i )
         Path += Acb_ObjPathD(p, iObj);
     p->nPaths = Path;
@@ -245,55 +204,39 @@ int Acb_ObjComputePathR( Acb_Ntk_t * p, int iObj )
 int Acb_NtkComputePathsR( Acb_Ntk_t * p, Vec_Int_t * vTfi )
 {
     int i, iObj, Path = 0;
-    if ( vTfi == NULL )
-    {
-        Acb_NtkCleanObjPathR( p );
-        Acb_NtkForEachCo( p, iObj, i )
-            if ( Acb_ObjLevelD(p, iObj) == p->LevelMax )
-                Acb_ObjSetPathR( p, iObj, 1 );
-        Acb_NtkForEachObjReverse( p, iObj )
-            if ( !Acb_ObjIsCo(p, iObj) && !Acb_ObjSlack(p, iObj) )
-                Acb_ObjComputePathR( p, iObj );
-    }
-    else
-    {
-        // it is assumed that vTfi contains CI nodes
-        assert( Acb_ObjSlack(p, Vec_IntEntry(vTfi, 0)) );
-        Vec_IntForEachEntryReverse( vTfi, iObj, i )
-            if ( !Acb_ObjSlack(p, iObj) )
-                Acb_ObjComputePathR( p, iObj );
-            else
-                Acb_ObjSetPathR( p, iObj, 0 );
-    }
+    // it is assumed that vTfi contains CI nodes
+    //assert( Acb_ObjSlack(p, Vec_IntEntry(vTfi, 0)) );
+    Vec_IntForEachEntryReverse( vTfi, iObj, i )
+        if ( !Acb_ObjSlack(p, iObj) )
+            Acb_ObjComputePathR( p, iObj );
+        else
+            Acb_ObjSetPathR( p, iObj, 0 );
     Acb_NtkForEachCi( p, iObj, i )
         Path += Acb_ObjPathR(p, iObj);
     assert( p->nPaths == Path );
     return Path;
 }
 
-
 int Acb_NtkComputePaths( Acb_Ntk_t * p )
 {
-    Acb_NtkComputeLevelD( p, NULL );
-    Acb_NtkComputeLevelR( p, NULL );
-    Acb_NtkComputePathsD( p, NULL );
-    Acb_NtkComputePathsR( p, NULL );
+    Vec_Int_t * vTfi = Acb_ObjCollectTfi( p, -1, 1 );
+    Vec_Int_t * vTfo = Acb_ObjCollectTfo( p, -1, 1 );
+    Acb_NtkComputeLevelD( p, vTfi );
+    Acb_NtkComputeLevelR( p, vTfo );
+    Acb_NtkComputePathsD( p, vTfi );
+    Acb_NtkComputePathsR( p, vTfo );
     return p->nPaths;
 }
-
 void Abc_NtkComputePaths( Abc_Ntk_t * p )
 {
     extern Acb_Ntk_t * Acb_NtkFromAbc( Abc_Ntk_t * p );
     Acb_Ntk_t * pNtk = Acb_NtkFromAbc( p );
-
     Acb_NtkCreateFanout( pNtk );
     printf( "Computed %d paths.\n", Acb_NtkComputePaths(pNtk) );
-
     Acb_ManFree( pNtk->pDesign );
 }
 
 
-
 /**Function*************************************************************
 
   Synopsis    []
@@ -305,42 +248,47 @@ void Abc_NtkComputePaths( Abc_Ntk_t * p )
   SeeAlso     []
 
 ***********************************************************************/
-int Acb_ObjPath( Acb_Ntk_t * p, int iObj )
-{
-    return Acb_ObjPathD(p, iObj) + Acb_ObjPathR(p, iObj);
-}
-void Acb_ObjUpdateTiming( Acb_Ntk_t * p, int iObj )
-{
-}
-void Acb_NtkUpdateTiming( Acb_Ntk_t * p, int iObj )
+void Acb_ObjUpdatePriority( Acb_Ntk_t * p, int iObj )
 {
-    int i, Entry;
-    if ( iObj > 0 )
+    int nPaths;
+    if ( p->vQue == NULL )
     {
-        // assuming that level of the new nodes is up to date
-        Vec_Int_t * vTfi = Acb_ObjCollectTfi( p, iObj, 1 );
-        Vec_Int_t * vTfo = Acb_ObjCollectTfo( p, iObj, 1 );
-        Acb_NtkComputeLevelD( p, vTfo );
-        Acb_NtkComputeLevelR( p, vTfi );
-        Acb_NtkComputePathsD( p, vTfo );
-        Acb_NtkComputePathsR( p, vTfi );
-        Vec_IntForEachEntry( vTfi, Entry, i )
-            Acb_ObjUpdateTiming( p, Entry );
-        Vec_IntForEachEntry( vTfo, Entry, i )
-            Acb_ObjUpdateTiming( p, Entry );
+        Acb_NtkCleanObjCounts( p );
+        p->vQue = Vec_QueAlloc( 1000 );
+        Vec_QueSetPriority( p->vQue, Vec_FltArrayP(&p->vCounts) );
     }
+    nPaths = Acb_ObjPathD(p, iObj) + Acb_ObjPathR(p, iObj);
+    if ( nPaths == 0 )
+        return;
+    Acb_ObjSetCounts( p, iObj, (float)nPaths );
+    if ( Vec_QueIsMember( p->vQue, iObj ) )
+        Vec_QueUpdate( p->vQue, iObj );
     else
+        Vec_QuePush( p->vQue, iObj );
+}
+void Acb_NtkUpdateTiming( Acb_Ntk_t * p, int iObj )
+{
+    int i, Entry, LevelMax = p->LevelMax;
+    // assuming that level of the new nodes is up to date
+    Vec_Int_t * vTfi = Acb_ObjCollectTfi( p, iObj, 1 );
+    Vec_Int_t * vTfo = Acb_ObjCollectTfo( p, iObj, 1 );
+    Acb_NtkComputeLevelD( p, vTfo );
+    Acb_NtkComputeLevelR( p, vTfi );
+    if ( iObj > 0 && LevelMax > p->LevelMax ) // reduced level
     {
-        Acb_NtkComputeLevelD( p, NULL );
-        Acb_NtkComputeLevelR( p, NULL );
-        Acb_NtkComputePathsD( p, NULL );
-        Acb_NtkComputePathsR( p, NULL );
-        Acb_NtkForEachNode( p, Entry )
-            Acb_ObjUpdateTiming( p, Entry );
+        vTfi = Acb_ObjCollectTfi( p, -1, 1 );
+        vTfo = Acb_ObjCollectTfo( p, -1, 1 );   
+        Vec_QueClear( p->vQue );
+        // add backup here
     }
+    Acb_NtkComputePathsD( p, vTfo );
+    Acb_NtkComputePathsR( p, vTfi );
+    Vec_IntForEachEntry( vTfi, Entry, i )
+        Acb_ObjUpdatePriority( p, Entry );
+    Vec_IntForEachEntry( vTfo, Entry, i )
+        Acb_ObjUpdatePriority( p, Entry );
 }
 
-
 /**Function*************************************************************
 
   Synopsis    []
@@ -352,20 +300,28 @@ void Acb_NtkUpdateTiming( Acb_Ntk_t * p, int iObj )
   SeeAlso     []
 
 ***********************************************************************/
+void Acb_NtkCreateNode( Acb_Ntk_t * p, word uTruth, Vec_Int_t * vSupp )
+{
+    int Pivot = Acb_ObjAlloc( p, ABC_OPER_LUT, Vec_IntSize(vSupp), 0 );
+    Acb_ObjSetTruth( p, Pivot, uTruth );
+    Acb_ObjAddFanins( p, Pivot, vSupp );
+    Acb_ObjAddFaninFanout( p, Pivot );
+    Acb_ObjComputeLevelD( p, Pivot );
+}
 void Acb_NtkUpdateNode( Acb_Ntk_t * p, int Pivot, word uTruth, Vec_Int_t * vSupp )
 {
-    int i, iFanin;
     Vec_WrdSetEntry( &p->vObjTruth, Pivot, uTruth );
-    Acb_ObjRemoveFanout( p, Pivot );
-    Acb_ObjRemoveFanins( p, Pivot );
-    Vec_IntForEachEntry( vSupp, iFanin, i )
-        Acb_ObjAddFanin( p, Pivot, iFanin );
-    Acb_ObjAddFanout( p, Pivot );
-    Acb_NtkUpdateTiming( p, Pivot );
     Vec_IntErase( Vec_WecEntry(&p->vCnfs, Pivot) );
+    Acb_ObjRemoveFaninFanout( p, Pivot );
+    Acb_ObjRemoveFanins( p, Pivot );
+    Acb_ObjAddFanins( p, Pivot, vSupp );
+    Acb_ObjAddFaninFanout( p, Pivot );
+    if ( p->vQue == NULL )
+        Acb_NtkUpdateLevelD( p, Pivot );
+    else
+        Acb_NtkUpdateTiming( p, Pivot );
 }
 
-
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////