Enabling reverse topo order in area minimization.

3 files changed, 107 insertions, 45 deletions

diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 4433c652..fffc10a0 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -5194,7 +5194,7 @@ int Abc_CommandMfs3( Abc_Frame_t * pAbc, int argc, char ** argv )
     // set defaults
     Sfm_ParSetDefault3( pPars );
     Extra_UtilGetoptReset();
-    while ( ( c = Extra_UtilGetopt( argc, argv, "IOVFKLHRMCNPWDdamzospdlvwh" ) ) != EOF )
+    while ( ( c = Extra_UtilGetopt( argc, argv, "IOVFKLHRMCNPWDarmzospdlvwh" ) ) != EOF )
     {
         switch ( c )
         {
@@ -5358,6 +5358,9 @@ int Abc_CommandMfs3( Abc_Frame_t * pAbc, int argc, char ** argv )
         case 'a':
             pPars->fArea ^= 1;
             break;
+        case 'r':
+            pPars->fAreaRev ^= 1;
+            break;
         case 'm':
             pPars->fUseAndOr ^= 1;
             break;
@@ -5406,7 +5409,7 @@ int Abc_CommandMfs3( Abc_Frame_t * pAbc, int argc, char ** argv )
     return 0;
 
 usage:
-    Abc_Print( -2, "usage: mfs3 [-IOVFKLHRMCNPWD <num>] [-amzospdlvwh]\n" );
+    Abc_Print( -2, "usage: mfs3 [-IOVFKLHRMCNPWD <num>] [-armzospdlvwh]\n" );
     Abc_Print( -2, "\t           performs don't-care-based optimization of mapped networks\n" );
     Abc_Print( -2, "\t-I <num> : the number of levels in the TFI cone (1 <= num) [default = %d]\n",             pPars->nTfiLevMax );
     Abc_Print( -2, "\t-O <num> : the number of levels in the TFO cone (0 <= num) [default = %d]\n",             pPars->nTfoLevMax );
@@ -5423,6 +5426,7 @@ usage:
     Abc_Print( -2, "\t-W <num> : size of timing window in percents (0 <= num <= 100) [default = %d]\n",         pPars->nTimeWin );
     Abc_Print( -2, "\t-D <num> : size of critical-timing delay-delta (in picoseconds) [default = %d]\n",        pPars->DeltaCrit );
     Abc_Print( -2, "\t-a       : toggle area minimization [default = %s]\n",                                    pPars->fArea? "yes": "no" );
+    Abc_Print( -2, "\t-r       : toggle using reverse topo order for area minimization [default = %s]\n",       pPars->fAreaRev? "yes": "no" );
     Abc_Print( -2, "\t-m       : toggle detecting multi-input AND/OR gates [default = %s]\n",                   pPars->fUseAndOr? "yes": "no" );
     Abc_Print( -2, "\t-z       : toggle zero-cost replacements [default = %s]\n",                               pPars->fZeroCost? "yes": "no" );
     Abc_Print( -2, "\t-o       : toggle using old implementation for comparison [default = %s]\n",              pPars->fRrOnly? "yes": "no" );
diff --git a/src/opt/sfm/sfm.h b/src/opt/sfm/sfm.h
index 02d12b3a..5f90e6c4 100644
--- a/src/opt/sfm/sfm.h
+++ b/src/opt/sfm/sfm.h
@@ -60,6 +60,7 @@ struct Sfm_Par_t_
     int             DeltaCrit;     // delay delta in picoseconds
     int             fRrOnly;       // perform redundance removal
     int             fArea;         // performs optimization for area
+    int             fAreaRev;      // performs optimization for area in reverse order
     int             fMoreEffort;   // performs high-affort minimization
     int             fUseAndOr;     // enable internal detection of AND/OR gates
     int             fZeroCost;     // enable zero-cost replacement
diff --git a/src/opt/sfm/sfmDec.c b/src/opt/sfm/sfmDec.c
index 8c809b3b..36a7b5b7 100644
--- a/src/opt/sfm/sfmDec.c
+++ b/src/opt/sfm/sfmDec.c
@@ -1699,7 +1699,7 @@ printf( "\n" );
 */  
     return nDivs;
 }
-void Sfm_DecInsert( Abc_Ntk_t * pNtk, Abc_Obj_t * pPivot, int Limit, Vec_Int_t * vGates, Vec_Wec_t * vFanins, Vec_Int_t * vMap, Vec_Ptr_t * vGateHandles, int GateBuf, int GateInv, Vec_Wrd_t * vFuncs, Vec_Int_t * vTimeNodes )
+Abc_Obj_t * Sfm_DecInsert( Abc_Ntk_t * pNtk, Abc_Obj_t * pPivot, int Limit, Vec_Int_t * vGates, Vec_Wec_t * vFanins, Vec_Int_t * vMap, Vec_Ptr_t * vGateHandles, int GateBuf, int GateInv, Vec_Wrd_t * vFuncs, Vec_Int_t * vTimeNodes )
 {
     Abc_Obj_t * pObjNew = NULL; 
     Vec_Int_t * vLevel;
@@ -1722,7 +1722,7 @@ void Sfm_DecInsert( Abc_Ntk_t * pNtk, Abc_Obj_t * pPivot, int Limit, Vec_Int_t *
             Abc_NtkUpdateIncLevel_rec( pObjNew );
             if ( vTimeNodes )
                 Vec_IntPush( vTimeNodes, Abc_ObjId(pObjNew) );
-            return;
+            return pObjNew;
         }
         else if ( vTimeNodes == NULL && Gate == GateInv )
         {
@@ -1755,7 +1755,7 @@ void Sfm_DecInsert( Abc_Ntk_t * pNtk, Abc_Obj_t * pPivot, int Limit, Vec_Int_t *
                 // update level
                 pObjNew->Level = 0;
                 Abc_NtkUpdateIncLevel_rec( pObjNew );
-                return;
+                return pObjNew;
             }
         }
     }
@@ -1776,6 +1776,7 @@ void Sfm_DecInsert( Abc_Ntk_t * pNtk, Abc_Obj_t * pPivot, int Limit, Vec_Int_t *
     // update level
     Abc_NtkForEachObjVecStart( vMap, pNtk, pObjNew, i, Limit )
         Abc_NtkUpdateIncLevel_rec( pObjNew );
+    return pObjNew;
 }
 void Sfm_DecPrintStats( Sfm_Dec_t * p )
 {
@@ -1846,57 +1847,108 @@ void Abc_NtkCountStats( Sfm_Dec_t * p, int Limit )
   SeeAlso     []
 
 ***********************************************************************/
-void Abc_NtkAreaOpt( Sfm_Dec_t * p )
+Abc_Obj_t * Abc_NtkAreaOptOne( Sfm_Dec_t * p, int i )
 {
+    abctime clk;
     Abc_Ntk_t * pNtk = p->pNtk;
     Sfm_Par_t * pPars = p->pPars;
-    Abc_Obj_t * pObj; 
-    abctime clk;
-    int i = 0, Limit, RetValue, nStop = Abc_NtkObjNumMax(pNtk);
-    Abc_NtkForEachNode( pNtk, pObj, i )
-    {
-        if ( i >= nStop || (pPars->nNodesMax && i > pPars->nNodesMax) )
-            break;
-        if ( pPars->nMffcMin > 1 && Abc_NodeMffcLabel(pObj) < pPars->nMffcMin )
-            continue;
-        if ( pPars->iNodeOne && i != pPars->iNodeOne )
-            continue;
-        if ( pPars->iNodeOne )
-            pPars->fVeryVerbose = (int)(i == pPars->iNodeOne);
-        p->nNodesTried++;
+    Abc_Obj_t * pObj = Abc_NtkObj( p->pNtk, i ); 
+    int Limit, RetValue, nStop = Abc_NtkObjNumMax(pNtk);
+    if ( pPars->nMffcMin > 1 && Abc_NodeMffcLabel(pObj) < pPars->nMffcMin )
+        return NULL;
+    if ( pPars->iNodeOne && i != pPars->iNodeOne )
+        return NULL;
+    if ( pPars->iNodeOne )
+        pPars->fVeryVerbose = (int)(i == pPars->iNodeOne);
+    p->nNodesTried++;
 clk = Abc_Clock();
-        p->nDivs = Sfm_DecExtract( pNtk, pPars, pObj, &p->vObjRoots, &p->vObjGates, &p->vObjFanins, &p->vObjMap, &p->vTemp, &p->vTemp2, &p->vObjMffc, &p->vObjInMffc, NULL );
+    p->nDivs = Sfm_DecExtract( pNtk, pPars, pObj, &p->vObjRoots, &p->vObjGates, &p->vObjFanins, &p->vObjMap, &p->vTemp, &p->vTemp2, &p->vObjMffc, &p->vObjInMffc, NULL );
 p->timeWin += Abc_Clock() - clk;
-        if ( pPars->nWinSizeMax && pPars->nWinSizeMax < Vec_IntSize(&p->vObjGates) )
-            continue;
-        p->nMffc = Vec_IntSize(&p->vObjMffc);
-        p->AreaMffc = Sfm_DecMffcArea(pNtk, &p->vObjMffc);
-        p->nMaxDivs = Abc_MaxInt( p->nMaxDivs, p->nDivs );
-        p->nAllDivs += p->nDivs;
-        p->iTarget = pObj->iTemp;
-        Limit = Vec_IntSize( &p->vObjGates );
-        p->nMaxWin = Abc_MaxInt( p->nMaxWin, Limit );
-        p->nAllWin += Limit;
+    if ( pPars->nWinSizeMax && pPars->nWinSizeMax < Vec_IntSize(&p->vObjGates) )
+        return NULL;
+    p->nMffc = Vec_IntSize(&p->vObjMffc);
+    p->AreaMffc = Sfm_DecMffcArea(pNtk, &p->vObjMffc);
+    p->nMaxDivs = Abc_MaxInt( p->nMaxDivs, p->nDivs );
+    p->nAllDivs += p->nDivs;
+    p->iTarget = pObj->iTemp;
+    Limit = Vec_IntSize( &p->vObjGates );
+    p->nMaxWin = Abc_MaxInt( p->nMaxWin, Limit );
+    p->nAllWin += Limit;
 clk = Abc_Clock();
-        RetValue = Sfm_DecPrepareSolver( p );
+    RetValue = Sfm_DecPrepareSolver( p );
 p->timeCnf += Abc_Clock() - clk;
-        if ( !RetValue )
-            continue;
+    if ( !RetValue )
+        return NULL;
 clk = Abc_Clock();
-        if ( pPars->fRrOnly )
-            RetValue = Sfm_DecPeformDec( p );
-        else
-            RetValue = Sfm_DecPeformDec2( p, pObj );
-        if ( p->pPars->fVeryVerbose )
-            printf( "\n\n" );
+    if ( pPars->fRrOnly )
+        RetValue = Sfm_DecPeformDec( p );
+    else
+        RetValue = Sfm_DecPeformDec2( p, pObj );
+    if ( p->pPars->fVeryVerbose )
+        printf( "\n\n" );
 p->timeSat += Abc_Clock() - clk;
-        if ( RetValue < 0 )
+    if ( RetValue < 0 )
+        return NULL;
+    p->nNodesChanged++;
+    Abc_NtkCountStats( p, Limit );
+    return Sfm_DecInsert( pNtk, pObj, Limit, &p->vObjGates, &p->vObjFanins, &p->vObjMap, &p->vGateHands, p->GateBuffer, p->GateInvert, &p->vGateFuncs, NULL );
+}
+void Abc_NtkAreaOpt( Sfm_Dec_t * p )
+{
+    Abc_Obj_t * pObj; 
+    int i, nStop = Abc_NtkObjNumMax(p->pNtk);
+    Abc_NtkForEachNode( p->pNtk, pObj, i )
+    {
+        if ( i >= nStop || (p->pPars->nNodesMax && i > p->pPars->nNodesMax) )
+            break;
+        Abc_NtkAreaOptOne( p, i );
+    }
+}
+void Abc_NtkAreaOpt2( Sfm_Dec_t * p )
+{
+    Abc_Obj_t * pObj, * pObjNew, * pFanin; 
+    int i, k, nStop = Abc_NtkObjNumMax(p->pNtk);
+    Vec_Ptr_t * vFront = Vec_PtrAlloc( 1000 );
+    Abc_NtkForEachObj( p->pNtk, pObj, i )
+        assert( pObj->fMarkB == 0 );
+    // start the queue of nodes to be tried
+    Abc_NtkForEachCo( p->pNtk, pObj, i )
+        if ( Abc_ObjIsNode(Abc_ObjFanin0(pObj)) && !Abc_ObjFanin0(pObj)->fMarkB )
+        {
+            Abc_ObjFanin0(pObj)->fMarkB = 1;
+            Vec_PtrPush( vFront, Abc_ObjFanin0(pObj) );
+        }
+    // process nodes in this order
+    Vec_PtrForEachEntry( Abc_Obj_t *, vFront, pObj, i )
+    {
+        if ( Abc_ObjIsNone(pObj) )
             continue;
-        p->nNodesChanged++;
-        Abc_NtkCountStats( p, Limit );
-        Sfm_DecInsert( pNtk, pObj, Limit, &p->vObjGates, &p->vObjFanins, &p->vObjMap, &p->vGateHands, p->GateBuffer, p->GateInvert, &p->vGateFuncs, NULL );
+        pObjNew = Abc_NtkAreaOptOne( p, Abc_ObjId(pObj) );
+        if ( pObjNew != NULL )
+        {
+            if ( !Abc_ObjIsNode(pObjNew) || Abc_ObjFaninNum(pObjNew) == 0 || pObjNew->fMarkB )
+                continue;
+            if ( (int)Abc_ObjId(pObjNew) < nStop )
+            {
+                pObjNew->fMarkB = 1;
+                Vec_PtrPush( vFront, pObjNew );
+                continue;
+            }
+        }
+        else
+            pObjNew = pObj;
+        Abc_ObjForEachFanin( pObjNew, pFanin, k )
+            if ( Abc_ObjIsNode(pFanin) && Abc_ObjFaninNum(pObjNew) > 0 && !pFanin->fMarkB )
+            {
+                pFanin->fMarkB = 1;
+                Vec_PtrPush( vFront, pFanin );
+            }
     }
+    Abc_NtkForEachObj( p->pNtk, pObj, i )
+        pObj->fMarkB = 0;
+    Vec_PtrFree( vFront );
 }
+
 void Abc_NtkDelayOpt( Sfm_Dec_t * p )
 {
     Abc_Ntk_t * pNtk = p->pNtk;
@@ -2018,7 +2070,12 @@ void Abc_NtkPerformMfs3( Abc_Ntk_t * pNtk, Sfm_Par_t * pPars )
     if ( pPars->fVerbose ) p->nTotalEdgesBeg = Abc_NtkGetTotalFanins(pNtk);
     // perform optimization
     if ( pPars->fArea )
-        Abc_NtkAreaOpt( p );
+    {
+        if ( pPars->fAreaRev )
+            Abc_NtkAreaOpt2( p );
+        else
+            Abc_NtkAreaOpt( p );
+    }
     else
         Abc_NtkDelayOpt( p );
     // record statistics