Adding iterative refinement to 'addbuffs'.

2 files changed, 161 insertions, 7 deletions

diff --git a/src/base/abc/abcUtil.c b/src/base/abc/abcUtil.c
index 33c97e83..df5b3978 100644
--- a/src/base/abc/abcUtil.c
+++ b/src/base/abc/abcUtil.c
@@ -2003,6 +2003,48 @@ void Abc_NtkPrintCiLevels( Abc_Ntk_t * pNtk )
     printf( "\n" );
 }
 
+
+/**Function*************************************************************
+
+  Synopsis    [Returns 1 if all other fanouts of pFanin are below pNode.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NtkAddBuffsEval( Abc_Obj_t * pNode, Abc_Obj_t * pFanin )
+{
+    Abc_Obj_t * pFanout;
+    int i;
+    Abc_ObjForEachFanout( pFanin, pFanout, i )
+        if ( pFanout != pNode && pFanout->Level >= pNode->Level )
+            return 0;
+    return 1;
+}
+/**Function*************************************************************
+
+  Synopsis    [Returns 1 if there exist a fanout of pFanin higher than pNode.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_NtkAddBuffsEval2( Abc_Obj_t * pNode, Abc_Obj_t * pFanin )
+{
+    Abc_Obj_t * pFanout;
+    int i;
+    Abc_ObjForEachFanout( pFanin, pFanout, i )
+        if ( pFanout != pNode && pFanout->Level > pNode->Level )
+            return 1;
+    return 0;
+}
+
 /**Function*************************************************************
 
   Synopsis    []
@@ -2030,12 +2072,12 @@ Abc_Obj_t * Abc_NtkAddBuffsOne( Vec_Ptr_t * vBuffs, Abc_Obj_t * pFanin, int Leve
     }
     return pBuffer;
 }
-Abc_Ntk_t * Abc_NtkAddBuffs( Abc_Ntk_t * pNtkInit, int fReverse, int fVerbose )
+Abc_Ntk_t * Abc_NtkAddBuffs( Abc_Ntk_t * pNtkInit, int fReverse, int nImprove, int fVerbose )
 {
     Vec_Ptr_t * vBuffs;
     Abc_Ntk_t * pNtk = Abc_NtkDup( pNtkInit );
     Abc_Obj_t * pObj, * pFanin, * pBuffer;
-    int i, k, nLevelMax = Abc_NtkLevel( pNtk );
+    int i, k, Iter, nLevelMax = Abc_NtkLevel( pNtk );
     Abc_NtkForEachCo( pNtk, pObj, i )
         pObj->Level = nLevelMax + 1;
     if ( fReverse )
@@ -2049,9 +2091,107 @@ Abc_Ntk_t * Abc_NtkAddBuffs( Abc_Ntk_t * pNtkInit, int fReverse, int fVerbose )
                 pObj->Level = Abc_MinInt( pFanin->Level - 1, pObj->Level );
             assert( pObj->Level > 0 );
         }
-        Vec_PtrFree( vNodes );
         Abc_NtkForEachCi( pNtk, pObj, i )
             pObj->Level = 0;
+
+        // move the nodes
+        for ( Iter = 0; Iter < nImprove; Iter++ )
+        {
+            int Counter = 0, TotalGain = 0;
+            Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+            {
+                int CountGain = -1;
+                assert( pObj->Level > 0 );
+                Abc_ObjForEachFanin( pObj, pFanin, k )
+                {
+                    assert( pFanin->Level < pObj->Level );
+                    if ( pFanin->Level + 1 == pObj->Level )
+                        break;
+                }
+                if ( k < Abc_ObjFaninNum(pObj) ) // cannot move
+                    continue;
+                Abc_ObjForEachFanin( pObj, pFanin, k )
+                    CountGain += Abc_NtkAddBuffsEval( pObj, pFanin );
+                if ( CountGain >= 0 ) // can move
+                {
+                    pObj->Level--;
+                    Counter++;
+                    TotalGain += CountGain;
+                }
+            }
+            if ( fVerbose )
+                printf( "Shifted %d nodes down with total gain %d.\n", Counter, TotalGain );
+            if ( Counter == 0 )
+                break;
+        }
+        Vec_PtrFree( vNodes );
+    }
+    else
+    {
+        // move the nodes
+        Vec_Ptr_t * vNodes = Abc_NtkDfs( pNtk, 1 );
+        for ( Iter = 0; Iter < nImprove; Iter++ )
+        {
+            int Counter = 0, TotalGain = 0;
+            Vec_PtrForEachEntryReverse( Abc_Obj_t *, vNodes, pObj, i )
+            {
+                int CountGain = 1;
+                assert( pObj->Level <= (unsigned)nLevelMax );
+                Abc_ObjForEachFanout( pObj, pFanin, k )
+                {
+                    assert( pFanin->Level > pObj->Level );
+                    if ( pFanin->Level == pObj->Level + 1 )
+                        break;
+                }
+                if ( k < Abc_ObjFanoutNum(pObj) ) // cannot move
+                    continue;
+                Abc_ObjForEachFanin( pObj, pFanin, k )
+                    CountGain -= !Abc_NtkAddBuffsEval2( pObj, pFanin );
+                if ( CountGain >= 0 ) // can move
+                {
+                    pObj->Level++;
+                    Counter++;
+                    TotalGain += CountGain;
+                }
+            } 
+            if ( fVerbose )
+                printf( "Shifted %d nodes up with total gain %d.\n", Counter, TotalGain );
+            if ( Counter == 0 )
+                break;
+        }
+/*
+        // move the nodes
+        for ( Iter = 0; Iter < nImprove; Iter++ )
+        {
+            int Counter = 0, TotalGain = 0;
+            Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
+            {
+                int CountGain = -1;
+                assert( pObj->Level > 0 );
+                Abc_ObjForEachFanin( pObj, pFanin, k )
+                {
+                    assert( pFanin->Level < pObj->Level );
+                    if ( pFanin->Level + 1 == pObj->Level )
+                        break;
+                }
+                if ( k < Abc_ObjFaninNum(pObj) ) // cannot move
+                    continue;
+                Abc_ObjForEachFanin( pObj, pFanin, k )
+                    CountGain += Abc_NtkAddBuffsEval( pObj, pFanin );
+                if ( CountGain >= 0 ) // can move
+                {
+                    pObj->Level--;
+                    Counter++;
+                    TotalGain += CountGain;
+                }
+            }
+            if ( fVerbose )
+                printf( "Shifted %d nodes down with total gain %d.\n", Counter, TotalGain );
+            if ( Counter == 0 )
+                break;
+        }
+*/
+        Vec_PtrFree( vNodes );
     }
     vBuffs = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) * (nLevelMax + 1) );
     Abc_NtkForEachObj( pNtk, pObj, i )
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index deb9bad1..2a7dbfc0 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -4550,19 +4550,32 @@ usage:
 ***********************************************************************/
 int Abc_CommandAddBuffs( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
-    extern Abc_Ntk_t * Abc_NtkAddBuffs( Abc_Ntk_t * pNtk, int fReverse, int fVerbose );
+    extern Abc_Ntk_t * Abc_NtkAddBuffs( Abc_Ntk_t * pNtk, int fReverse, int nImprove, int fVerbose );
     Abc_Ntk_t * pNtk = Abc_FrameReadNtk(pAbc);
     Abc_Ntk_t * pNtkRes;
     int c, fVerbose;
     int fReverse;
+    int nImprove;
 
+    nImprove = 1000;
     fReverse = 0;
     fVerbose = 0;
     Extra_UtilGetoptReset();
-    while ( ( c = Extra_UtilGetopt( argc, argv, "rvh" ) ) != EOF )
+    while ( ( c = Extra_UtilGetopt( argc, argv, "Irvh" ) ) != EOF )
     {
         switch ( c )
         {
+        case 'I':
+            if ( globalUtilOptind >= argc )
+            {
+                Abc_Print( -1, "Command line switch \"-I\" should be followed by a positive integer.\n" );
+                goto usage;
+            }
+            nImprove = atoi(argv[globalUtilOptind]);
+            globalUtilOptind++;
+            if ( nImprove < 0 ) 
+                goto usage;
+            break;
         case 'r':
             fReverse ^= 1;
             break;
@@ -4588,7 +4601,7 @@ int Abc_CommandAddBuffs( Abc_Frame_t * pAbc, int argc, char ** argv )
     }
 
     // modify the current network
-    pNtkRes = Abc_NtkAddBuffs( pNtk, fReverse, fVerbose );
+    pNtkRes = Abc_NtkAddBuffs( pNtk, fReverse, nImprove, fVerbose );
     if ( pNtkRes == NULL )
     {
         Abc_Print( -1, "The command has failed.\n" );
@@ -4599,8 +4612,9 @@ int Abc_CommandAddBuffs( Abc_Frame_t * pAbc, int argc, char ** argv )
     return 0;
 
 usage:
-    Abc_Print( -2, "usage: addbuffs [-rvh]\n" );
+    Abc_Print( -2, "usage: addbuffs [-I num] [-rvh]\n" );
     Abc_Print( -2, "\t           adds buffers to create balanced CI/CO paths\n" );
+    Abc_Print( -2, "\t-I <num> : the number of refinement iterations [default = %d]\n", nImprove );
     Abc_Print( -2, "\t-r       : toggle reversing the levelized order [default = %s]\n", fReverse? "yes": "no" );
     Abc_Print( -2, "\t-v       : toggle printing optimization summary [default = %s]\n", fVerbose? "yes": "no" );
     Abc_Print( -2, "\t-h       : print the command usage\n");