| /**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 |
| |
