Version abc70706

1 files changed, 188 insertions, 42 deletions

diff --git a/src/base/abci/abcTiming.c b/src/base/abci/abcTiming.c
index 93fa3fa5..fd54f519 100644
--- a/src/base/abci/abcTiming.c
+++ b/src/base/abci/abcTiming.c
@@ -630,39 +630,133 @@ void Abc_NodeDelayTraceArrival( Abc_Obj_t * pNode )
 
 /**Function*************************************************************
 
-  Synopsis    [Prepares the AIG for the comptuation of required levels.]
+  Synopsis    [Computes the level of the node using its fanin levels.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_ObjLevelNew( Abc_Obj_t * pObj )
+{
+    Abc_Obj_t * pFanin;
+    int i, Level = 0;
+    Abc_ObjForEachFanin( pObj, pFanin, i )
+        Level = ABC_MAX( Level, Abc_ObjLevel(pFanin) );
+    return Level + 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Computes the reverse level of the node using its fanout levels.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_ObjReverseLevelNew( Abc_Obj_t * pObj )
+{
+    Abc_Obj_t * pFanout;
+    int i, LevelCur, Level = 0;
+    Abc_ObjForEachFanout( pObj, pFanout, i )
+    {
+        LevelCur = Abc_ObjReverseLevel( pFanout );
+        Level = ABC_MAX( Level, LevelCur );
+    }
+    return Level + 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Returns required level of the node.]
+
+  Description [Converts the reverse levels of the node into its required 
+  level as follows: ReqLevel(Node) = MaxLevels(Ntk) + 1 - LevelR(Node).]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_ObjRequiredLevel( Abc_Obj_t * pObj )
+{
+    Abc_Ntk_t * pNtk = pObj->pNtk;
+    assert( pNtk->vLevelsR );
+    return pNtk->LevelMax + 1 - Abc_ObjReverseLevel(pObj);
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Returns the reverse level of the node.]
+
+  Description [The reverse level is the level of the node in reverse
+  topological order, starting from the COs.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_ObjReverseLevel( Abc_Obj_t * pObj )
+{
+    Abc_Ntk_t * pNtk = pObj->pNtk;
+    assert( pNtk->vLevelsR );
+    Vec_IntFillExtra( pNtk->vLevelsR, pObj->Id + 1, 0 );
+    return Vec_IntEntry(pNtk->vLevelsR, pObj->Id);
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Sets the reverse level of the node.]
+
+  Description [The reverse level is the level of the node in reverse
+  topological order, starting from the COs.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_ObjSetReverseLevel( Abc_Obj_t * pObj, int LevelR )
+{
+    Abc_Ntk_t * pNtk = pObj->pNtk;
+    assert( pNtk->vLevelsR );
+    Vec_IntFillExtra( pNtk->vLevelsR, pObj->Id + 1, 0 );
+    Vec_IntWriteEntry( pNtk->vLevelsR, pObj->Id, LevelR );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Prepares for the computation of required levels.]
 
   Description [This procedure should be called before the required times
   are used. It starts internal data structures, which records the level 
-  from the COs of the AIG nodes in reverse topologogical order.]
+  from the COs of the network nodes in reverse topologogical order.]
                
   SideEffects []
 
   SeeAlso     []
 
 ***********************************************************************/
-void Abc_NtkStartReverseLevels( Abc_Ntk_t * pNtk )
+void Abc_NtkStartReverseLevels( Abc_Ntk_t * pNtk, int nMaxLevelIncrease )
 {
     Vec_Ptr_t * vNodes;
-    Abc_Obj_t * pObj, * pFanout;
-    int i, k, nLevelsCur;
-//    assert( Abc_NtkIsStrash(pNtk) );
+    Abc_Obj_t * pObj;
+    int i;
     // remember the maximum number of direct levels
-//    pNtk->LevelMax = Abc_AigLevel(pNtk);
-    pNtk->LevelMax = Abc_NtkLevel(pNtk);
+    pNtk->LevelMax = Abc_NtkLevel(pNtk) + nMaxLevelIncrease;
     // start the reverse levels
     pNtk->vLevelsR = Vec_IntAlloc( 0 );
-    Vec_IntFill( pNtk->vLevelsR, Abc_NtkObjNumMax(pNtk), 0 );
+    Vec_IntFill( pNtk->vLevelsR, 1 + Abc_NtkObjNumMax(pNtk), 0 );
     // compute levels in reverse topological order
     vNodes = Abc_NtkDfsReverse( pNtk );
     Vec_PtrForEachEntry( vNodes, pObj, i )
-    {
-        nLevelsCur = 0;
-        Abc_ObjForEachFanout( pObj, pFanout, k )
-            if ( nLevelsCur < Vec_IntEntry(pNtk->vLevelsR, pFanout->Id) )
-                nLevelsCur = Vec_IntEntry(pNtk->vLevelsR, pFanout->Id);
-        Vec_IntWriteEntry( pNtk->vLevelsR, pObj->Id, nLevelsCur + 1 );
-    }
+        Abc_ObjSetReverseLevel( pObj, Abc_ObjReverseLevelNew(pObj) );
     Vec_PtrFree( vNodes );
 }
 
@@ -688,64 +782,116 @@ void Abc_NtkStopReverseLevels( Abc_Ntk_t * pNtk )
 
 /**Function*************************************************************
 
-  Synopsis    [Sets the reverse level of the node.]
+  Synopsis    [Incrementally updates level of the nodes.]
 
-  Description [The reverse level is the level of the node in reverse
-  topological order, starting from the COs.]
+  Description []
                
   SideEffects []
 
   SeeAlso     []
 
 ***********************************************************************/
-void Abc_NodeSetReverseLevel( Abc_Obj_t * pObj, int LevelR )
+void Abc_NtkUpdateLevel( Abc_Obj_t * pObjNew, Vec_Vec_t * vLevels )
 {
-    Abc_Ntk_t * pNtk = pObj->pNtk;
-    assert( Abc_NtkIsStrash(pNtk) );
-    assert( pNtk->vLevelsR );
-    Vec_IntFillExtra( pNtk->vLevelsR, pObj->Id + 1, 0 );
-    Vec_IntWriteEntry( pNtk->vLevelsR, pObj->Id, LevelR );
+    Abc_Obj_t * pFanout, * pTemp;
+    int LevelOld, Lev, k, m;
+    // check if level has changed
+    LevelOld = Abc_ObjLevel(pObjNew);
+    if ( LevelOld == Abc_ObjLevelNew(pObjNew) )
+        return;
+    // start the data structure for level update
+    // we cannot fail to visit a node when using this structure because the 
+    // nodes are stored by their _old_ levels, which are assumed to be correct
+    Vec_VecClear( vLevels );
+    Vec_VecPush( vLevels, LevelOld, pObjNew );
+    pObjNew->fMarkA = 1;
+    // recursively update level
+    Vec_VecForEachEntryStart( vLevels, pTemp, Lev, k, LevelOld )
+    {
+        pTemp->fMarkA = 0;
+        assert( Abc_ObjLevel(pTemp) == Lev );
+        Abc_ObjSetLevel( pTemp, Abc_ObjLevelNew(pTemp) );
+        // if the level did not change, to need to check the fanout levels
+        if ( Abc_ObjLevel(pTemp) == Lev )
+            continue;
+        // schedule fanout for level update
+        Abc_ObjForEachFanout( pTemp, pFanout, m )
+        {
+            if ( !Abc_ObjIsCo(pFanout) && !pFanout->fMarkA )
+            {
+                Vec_VecPush( vLevels, Abc_ObjLevel(pFanout), pFanout );
+                pFanout->fMarkA = 1;
+            }
+        }
+    }
 }
 
 /**Function*************************************************************
 
-  Synopsis    [Returns the reverse level of the node.]
+  Synopsis    [Incrementally updates level of the nodes.]
 
-  Description [The reverse level is the level of the node in reverse
-  topological order, starting from the COs.]
+  Description []
                
   SideEffects []
 
   SeeAlso     []
 
 ***********************************************************************/
-int Abc_NodeReadReverseLevel( Abc_Obj_t * pObj )
+void Abc_NtkUpdateReverseLevel( Abc_Obj_t * pObjNew, Vec_Vec_t * vLevels )
 {
-    Abc_Ntk_t * pNtk = pObj->pNtk;
-    assert( Abc_NtkIsStrash(pNtk) );
-    assert( pNtk->vLevelsR );
-    Vec_IntFillExtra( pNtk->vLevelsR, pObj->Id + 1, 0 );
-    return Vec_IntEntry(pNtk->vLevelsR, pObj->Id);
+    Abc_Obj_t * pFanin, * pTemp;
+    int LevelOld, Lev, k, m;
+    // check if level has changed
+    LevelOld = Abc_ObjReverseLevel(pObjNew);
+    if ( LevelOld == Abc_ObjReverseLevelNew(pObjNew) )
+        return;
+    // start the data structure for level update
+    // we cannot fail to visit a node when using this structure because the 
+    // nodes are stored by their _old_ levels, which are assumed to be correct
+    Vec_VecClear( vLevels );
+    Vec_VecPush( vLevels, LevelOld, pObjNew );
+    pObjNew->fMarkA = 1;
+    // recursively update level
+    Vec_VecForEachEntryStart( vLevels, pTemp, Lev, k, LevelOld )
+    {
+        pTemp->fMarkA = 0;
+        LevelOld = Abc_ObjReverseLevel(pTemp); 
+        assert( LevelOld == Lev );
+        Abc_ObjSetReverseLevel( pTemp, Abc_ObjReverseLevelNew(pTemp) );
+        // if the level did not change, to need to check the fanout levels
+        if ( Abc_ObjReverseLevel(pTemp) == Lev )
+            continue;
+        // schedule fanins for level update
+        Abc_ObjForEachFanin( pTemp, pFanin, m )
+        {
+            if ( !Abc_ObjIsCi(pFanin) && !pFanin->fMarkA )
+            {
+                Vec_VecPush( vLevels, Abc_ObjReverseLevel(pFanin), pFanin );
+                pFanin->fMarkA = 1;
+            }
+        }
+    }
 }
 
 /**Function*************************************************************
 
-  Synopsis    [Returns required level of the node.]
+  Synopsis    [Replaces the node and incrementally updates levels.]
 
-  Description [Converts the reverse levels of the node into its required 
-  level as follows: ReqLevel(Node) = MaxLevels(Ntk) + 1 - LevelR(Node).]
+  Description []
                
   SideEffects []
 
   SeeAlso     []
 
 ***********************************************************************/
-int Abc_NodeReadRequiredLevel( Abc_Obj_t * pObj )
+void Abc_NtkUpdate( Abc_Obj_t * pObj, Abc_Obj_t * pObjNew, Vec_Vec_t * vLevels )
 {
-    Abc_Ntk_t * pNtk = pObj->pNtk;
-    assert( Abc_NtkIsStrash(pNtk) );
-    assert( pNtk->vLevelsR );
-    return pNtk->LevelMax + 1 - Vec_IntEntry(pNtk->vLevelsR, pObj->Id);
+    // replace the old node by the new node
+    pObjNew->Level = pObj->Level;
+    Abc_ObjReplace( pObj, pObjNew );
+    // update the level of the node
+    Abc_NtkUpdateLevel( pObjNew, vLevels );
+    Abc_NtkUpdateReverseLevel( pObjNew, vLevels );
 }
 
 ////////////////////////////////////////////////////////////////////////