New feature for area minimization in standard cell mapping.

3 files changed, 387 insertions, 1 deletions

diff --git a/src/opt/sfm/module.make b/src/opt/sfm/module.make
index fbdaa2ec..66518e4e 100644
--- a/src/opt/sfm/module.make
+++ b/src/opt/sfm/module.make
@@ -1,4 +1,5 @@
-SRC +=    src/opt/sfm/sfmCnf.c \
+SRC +=    src/opt/sfm/sfmArea.c \
+    src/opt/sfm/sfmCnf.c \
     src/opt/sfm/sfmCore.c \
     src/opt/sfm/sfmDec.c \
     src/opt/sfm/sfmLib.c \
diff --git a/src/opt/sfm/sfmArea.c b/src/opt/sfm/sfmArea.c
new file mode 100644
index 00000000..87f3b511
--- /dev/null
+++ b/src/opt/sfm/sfmArea.c
@@ -0,0 +1,380 @@
+/**CFile****************************************************************
+
+  FileName    [sfmArea.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [SAT-based optimization using internal don't-cares.]
+
+  Synopsis    [Area optimization.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 20, 2005.]
+
+  Revision    [$Id: sfmArea.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "sfmInt.h"
+#include "map/mio/mio.h"
+#include "misc/util/utilTruth.h"
+#include "misc/util/utilNam.h"
+#include "map/scl/sclLib.h"
+#include "map/scl/sclCon.h"
+#include "opt/dau/dau.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Precompute cell parameters.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Vec_Int_t * Abc_NtkPrecomputeCellPairs( Mio_Cell2_t * pCells, int nCells )
+{
+    Vec_Int_t * vInfo = Vec_IntAlloc( 1000 );
+    word iBestArea, tCur, iThis;
+    int * pPerm[7], nPerms[7], Perm[7], * Perm1, * Perm2;
+    int iBestCell, iBestPerm, iBestDiff;
+    int i, k, n, v, p, Count = 0;
+    int iGate1 = -1, iGate2 = -1;
+
+    for ( i = 1; i <= 6; i++ )
+        pPerm[i] = Extra_PermSchedule( i );
+    for ( i = 1; i <= 6; i++ )
+        nPerms[i] = Extra_Factorial( i );
+
+    for ( i = 2; i < nCells; i++ )
+    {
+        int nFanins = pCells[i].nFanins;
+        for ( n = 0; n <= nFanins; n++ )
+        {
+            // get the truth table
+            iThis = (n == nFanins) ? ~pCells[i].uTruth : Abc_Tt6Flip(pCells[i].uTruth, n);
+            // init the comparison
+            iBestArea = ~((word)0);
+            iBestCell = iBestPerm = iBestDiff = -1;
+            // iterate through cells
+            for ( k = 2; k < nCells; k++ )
+            {
+                if ( nFanins != (int)pCells[k].nFanins )
+                    continue;
+                if ( i != k && pCells[i].uTruth == pCells[k].uTruth )
+                {
+                    iGate1 = i;
+                    iGate2 = k;
+                    Count++;
+                    continue;
+                }
+                // set unit permutation
+                for ( v = 0; v < nFanins; v++ )
+                    Perm[v] = v;
+                // go through all permutation of Cell[k]
+                tCur = pCells[k].uTruth;
+                for ( p = 0; p < nPerms[nFanins]; p++ )
+                {
+                    if ( iThis == tCur && iBestArea > pCells[k].AreaW ) 
+                    {
+                        iBestArea = pCells[k].AreaW;
+                        iBestCell = k;
+                        iBestPerm = 0;
+                        for ( v = 0; v < nFanins; v++ )
+                            iBestPerm |= (v << (Perm[v] << 2));
+                        iBestDiff = (pCells[i].AreaW >= pCells[k].AreaW) ? (int)(pCells[i].AreaW - pCells[k].AreaW) : -(int)(pCells[k].AreaW - pCells[i].AreaW);
+                    }
+                    if ( nPerms[nFanins] == 1 )
+                        continue;
+                    // update
+                    tCur  = Abc_Tt6SwapAdjacent( tCur, pPerm[nFanins][p] );
+                    Perm1 = Perm + pPerm[nFanins][p];
+                    Perm2 = Perm1 + 1;
+                    ABC_SWAP( int, *Perm1, *Perm2 );
+                }
+                assert( tCur == pCells[k].uTruth );
+            }
+            Vec_IntPushThree( vInfo, iBestCell, iBestPerm, iBestDiff );
+        }
+    }
+
+    for ( i = 1; i <= 6; i++ )
+        ABC_FREE( pPerm[i] );
+    if ( Count )
+        printf( "In this library, %d cell pairs have equal functions (for example, %s and %s).\n", Count/2, pCells[iGate1].pName, pCells[iGate2].pName );
+    return vInfo;
+}
+Vec_Int_t * Abc_NtkPrecomputeFirsts( Mio_Cell2_t * pCells, int nCells )
+{
+    int i, Index = 0;
+    Vec_Int_t * vFirst = Vec_IntStartFull( 2 ); 
+    for ( i = 2; i < nCells; i++ )
+    {
+        Vec_IntPush( vFirst, Index );
+        Index += 3 * (pCells[i].nFanins + 1);
+    }
+    assert( nCells == Vec_IntSize(vFirst) );
+    return vFirst;
+}
+int Abc_NtkPrecomputePrint( Mio_Cell2_t * pCells, int nCells, Vec_Int_t * vInfo )
+{
+    int i, n, v, Index = 0, nRecUsed = 0;
+    for ( i = 2; i < nCells; i++ )
+    {
+        int nFanins = pCells[i].nFanins;
+        printf( "%3d : %8s   Fanins = %d   ", i, pCells[i].pName, nFanins );
+        Dau_DsdPrintFromTruth( &pCells[i].uTruth, nFanins );
+        for ( n = 0; n <= nFanins; n++, Index += 3 )
+        {
+            int iCellA = Vec_IntEntry( vInfo, Index+0 );
+            int iPerm  = Vec_IntEntry( vInfo, Index+1 );
+            int Diff   = Vec_IntEntry( vInfo, Index+2 );
+            if ( iCellA == -1 )
+                continue;
+            printf( "%d : {", n );
+            for ( v = 0; v < nFanins; v++ )
+                printf( " %d ", (iPerm >> (v << 2)) & 15 );
+            printf( "}  Index = %d  ", Index );
+
+            printf( "Gain = %6.2f  ", Scl_Int2Flt(Diff) );
+            Dau_DsdPrintFromTruth( &pCells[iCellA].uTruth, pCells[iCellA].nFanins );
+            nRecUsed++;
+        }
+    }
+    return nRecUsed;
+}
+
+void Abc_NtkPrecomputeCellPairsTest()
+{
+    int nCells;
+    Mio_Cell2_t * pCells = Mio_CollectRootsNewDefault2( 6, &nCells, 0 );
+    Vec_Int_t * vInfo = Abc_NtkPrecomputeCellPairs( pCells, nCells );
+    int nRecUsed = Abc_NtkPrecomputePrint( pCells, nCells, vInfo );
+    // iterate through the cells
+    Vec_Int_t * vFirst = Abc_NtkPrecomputeFirsts( pCells, nCells );
+    printf( "Used records = %d.  All records = %d.\n", nRecUsed, Vec_IntSize(vInfo)/3 - nRecUsed );
+    assert( nCells == Vec_IntSize(vFirst) );
+    Vec_IntFree( vFirst );
+    Vec_IntFree( vInfo );
+    ABC_FREE( pCells );
+}
+
+int Abc_NodeCheckFanoutHasFanin( Abc_Obj_t * pNode, Abc_Obj_t * pFanin )
+{
+    Abc_Obj_t * pThis;
+    int i;
+    Abc_ObjForEachFanout( pNode, pThis, i )
+        if ( Abc_NodeFindFanin(pThis, pFanin) >= 0 )
+            return i;
+    return -1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Evaluate changes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_ObjHasDupFanins( Abc_Obj_t * pObj )
+{
+    int * pArray = pObj->vFanins.pArray;
+    int i, k, Limit = Abc_ObjFaninNum(pObj);
+    for ( i = 0; i < Limit; i++ )
+        for ( k = i+1; k < Limit; k++ )
+            if ( pArray[i] == pArray[k] )
+                return 1;
+    return 0;
+}
+int Abc_ObjHasDupFanouts( Abc_Obj_t * pObj )
+{
+    int * pArray = pObj->vFanouts.pArray;
+    int i, k, Limit = Abc_ObjFanoutNum(pObj);
+    for ( i = 0; i < Limit; i++ )
+        for ( k = i+1; k < Limit; k++ )
+            if ( pArray[i] == pArray[k] )
+                return 1;
+    return 0;
+}
+int Abc_ObjChangeEval( Abc_Obj_t * pObj, Vec_Int_t * vInfo, Vec_Int_t * vFirst, int InvArea, int * pfUseInv )
+{
+    Abc_Obj_t * pNext;
+    Mio_Gate_t * pGate = (Mio_Gate_t *)pObj->pData;
+    int iFanCell, iNodeCell = Mio_GateReadCell( (Mio_Gate_t *)pObj->pData );
+    int * pFanInfo, * pNodeInfo = Vec_IntEntryP( vInfo, Vec_IntEntry(vFirst, iNodeCell) );
+    int i, fNeedInv = 0, Gain = 0, iFanin = Abc_ObjFaninNum(pObj), fUseInv = Abc_NodeIsInv(pObj);
+    assert( iFanin > 0 );
+    *pfUseInv = 0;
+    if ( pNodeInfo[3*iFanin] == -1 )
+        return 0;
+    if ( fUseInv )
+        Gain = InvArea;
+    else
+        Gain = pNodeInfo[3*iFanin+2];
+    Abc_ObjForEachFanout( pObj, pNext, i )
+    {
+        if ( fUseInv && Abc_NodeFindFanin(pNext, Abc_ObjFanin0(pObj)) >= 0 )
+            return 0;
+        if ( Abc_ObjHasDupFanins(pNext) )
+            return 0;
+        if ( !Abc_ObjIsNode(pNext) || Abc_NodeIsBuf(pNext) )
+        {
+            fNeedInv = 1;
+            continue;
+        }
+        if ( Abc_NodeIsInv(pNext) )
+        {
+            if ( Abc_NodeCheckFanoutHasFanin(pNext, pObj) >= 0 )
+                return 0;
+            Gain += InvArea;
+            continue;
+        }
+        iFanCell = Mio_GateReadCell( (Mio_Gate_t *)pNext->pData );
+        pFanInfo = Vec_IntEntryP( vInfo, Vec_IntEntry(vFirst, iFanCell) );
+        iFanin   = Abc_NodeFindFanin( pNext, pObj );
+        if ( pFanInfo[3*iFanin] == -1 )
+        {
+            fNeedInv = 1;
+            continue;
+        }
+        Gain += pFanInfo[3*iFanin+2];
+    }
+    if ( fNeedInv )
+        Gain -= InvArea;
+    *pfUseInv = fNeedInv;
+    return Gain;
+}
+void Abc_ObjChangeUpdate( Abc_Obj_t * pObj, int iFanin, Mio_Cell2_t * pCells, int * pNodeInfo, Vec_Int_t * vTemp )
+{
+    int v, Perm, iNodeCell = pNodeInfo[3*iFanin];
+    Mio_Gate_t * pGate = (Mio_Gate_t *)pObj->pData;
+    //Abc_ObjPrint( stdout, pObj );
+    //printf( "Replacing fanout %d with %s by %s with fanin %d.\n", Abc_ObjId(pObj), Mio_GateReadName(pGate), Mio_GateReadName((Mio_Gate_t *)pCells[iNodeCell].pMioGate), iFanin );
+    pObj->pData = (Mio_Gate_t *)pCells[iNodeCell].pMioGate;
+    Perm = pNodeInfo[3*iFanin+1];
+    Vec_IntClear( vTemp );
+    for ( v = 0; v < Abc_ObjFaninNum(pObj); v++ )
+        Vec_IntPush( vTemp, Abc_ObjFaninId(pObj, (Perm >> (v << 2)) & 15) );
+    Vec_IntClear( &pObj->vFanins );
+    Vec_IntAppend( &pObj->vFanins, vTemp );
+}
+void Abc_ObjChangePerform( Abc_Obj_t * pObj, Vec_Int_t * vInfo, Vec_Int_t * vFirst, int fUseInv, Vec_Int_t * vTemp, Vec_Ptr_t * vFanout, Vec_Ptr_t * vFanout2, Mio_Cell2_t * pCells )
+{
+    Abc_Obj_t * pNext, * pNext2, * pNodeInv = NULL;
+    int iFanCell, iNodeCell = Mio_GateReadCell( (Mio_Gate_t *)pObj->pData );
+    int * pFanInfo, * pNodeInfo = Vec_IntEntryP( vInfo, Vec_IntEntry(vFirst, iNodeCell) );
+    int i, k, iFanin = Abc_ObjFaninNum(pObj);
+    assert( iFanin > 0 && pNodeInfo[3*iFanin] != -1 );
+    // update the node
+    Abc_NodeCollectFanouts( pObj, vFanout );
+    if ( Abc_NodeIsInv(pObj) )
+    {
+        Abc_Obj_t * pFanin = Abc_ObjFanin0(pObj);
+        Vec_PtrForEachEntry( Abc_Obj_t *, vFanout, pNext, k )
+            Abc_ObjPatchFanin( pNext, pObj, pFanin );
+        assert( Abc_ObjFanoutNum(pObj) == 0 );
+        Abc_NtkDeleteObj(pObj);
+        pObj = pFanin;
+        assert( fUseInv == 0 );
+    }
+    else
+        Abc_ObjChangeUpdate( pObj, iFanin, pCells, pNodeInfo, vTemp );
+    // add inverter if needed
+    if ( fUseInv )
+        pNodeInv = Abc_NtkCreateNodeInv(pObj->pNtk, pObj);
+    // update the fanouts
+    Vec_PtrForEachEntry( Abc_Obj_t *, vFanout, pNext, i )
+    {
+        if ( !Abc_ObjIsNode(pNext) || Abc_NodeIsBuf(pNext) )
+        {
+            Abc_ObjPatchFanin( pNext, pObj, pNodeInv );
+            continue;
+        }
+        if ( Abc_NodeIsInv(pNext) )
+        {
+            Abc_NodeCollectFanouts( pNext, vFanout2 );
+            Vec_PtrForEachEntry( Abc_Obj_t *, vFanout2, pNext2, k )
+                Abc_ObjPatchFanin( pNext2, pNext, pObj );
+            assert( Abc_ObjFanoutNum(pNext) == 0 );
+            Abc_NtkDeleteObj(pNext);
+            continue;
+        }
+        iFanin   = Abc_NodeFindFanin( pNext, pObj );
+        iFanCell = Mio_GateReadCell( (Mio_Gate_t *)pNext->pData );
+        pFanInfo = Vec_IntEntryP( vInfo, Vec_IntEntry(vFirst, iFanCell) );
+        if ( pFanInfo[3*iFanin] == -1 )
+        {
+            Abc_ObjPatchFanin( pNext, pObj, pNodeInv );
+            continue;
+        }
+        Abc_ObjChangeUpdate( pNext, iFanin, pCells, pFanInfo, vTemp );
+    }
+}
+void Abc_NtkChangePerform( Abc_Ntk_t * pNtk, int fVerbose )
+{
+    abctime clk = Abc_Clock();
+    int i, fNeedInv, nCells, Gain, GainAll = 0, Count = 0, CountInv = 0;
+    Mio_Cell2_t * pCells = Mio_CollectRootsNewDefault2( 6, &nCells, 0 );
+    Vec_Int_t * vInfo = Abc_NtkPrecomputeCellPairs( pCells, nCells );
+    Vec_Int_t * vFirst = Abc_NtkPrecomputeFirsts( pCells, nCells );
+
+    Vec_Ptr_t * vFanout = Vec_PtrAlloc( 100 );
+    Vec_Ptr_t * vFanout2 = Vec_PtrAlloc( 100 );
+    Vec_Int_t * vTemp = Vec_IntAlloc( 100 );
+    Abc_Obj_t * pObj;
+    Abc_NtkForEachNode( pNtk, pObj, i )
+    {
+        if ( Abc_ObjFaninNum(pObj) < 2 && !Abc_NodeIsInv(pObj) )
+            continue;
+        if ( Abc_ObjHasDupFanouts(pObj) )
+            continue;
+        Gain = Abc_ObjChangeEval( pObj, vInfo, vFirst, (int)pCells[3].AreaW, &fNeedInv );
+        if ( Gain <= 0 )
+            continue;
+        //printf( "Obj %d\n", Abc_ObjId(pObj) );
+        Count++;
+        CountInv += Abc_NodeIsInv(pObj);
+        GainAll += Gain;
+        Abc_ObjChangePerform( pObj, vInfo, vFirst, fNeedInv, vTemp, vFanout, vFanout2, pCells );
+    }
+    Vec_PtrFree( vFanout2 );
+    Vec_PtrFree( vFanout );
+    Vec_IntFree( vTemp );
+
+    Vec_IntFree( vFirst );
+    Vec_IntFree( vInfo );
+    ABC_FREE( pCells );
+
+    if ( fVerbose )
+        printf( "Total gain in area = %6.2f after %d changes (including %d inverters). ", Scl_Int2Flt(GainAll), Count, CountInv );
+    if ( fVerbose )
+        Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/opt/sfm/sfmDec.c b/src/opt/sfm/sfmDec.c
index bce20624..c5af0ac0 100644
--- a/src/opt/sfm/sfmDec.c
+++ b/src/opt/sfm/sfmDec.c
@@ -2152,6 +2152,11 @@ void Abc_NtkPerformMfs3( Abc_Ntk_t * pNtk, Sfm_Par_t * pPars )
     if ( pPars->fLibVerbose )
         Sfm_LibPrint( p->pLib );
     Sfm_DecStop( p );
+    if ( pPars->fArea )
+    {
+        extern void Abc_NtkChangePerform( Abc_Ntk_t * pNtk, int fVerbose );
+        Abc_NtkChangePerform( pNtk, pPars->fVerbose );
+    }
 }
 
 ////////////////////////////////////////////////////////////////////////