sfmArea.c

Go to the documentation of this file.

 
#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
 



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;
}

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 );
}

 
 
ABC_NAMESPACE_IMPL_END