| /**CFile**************************************************************** |
| |
| FileName [giaResub.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [Scalable AIG package.] |
| |
| Synopsis [Resubstitution.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: giaResub.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "gia.h" |
| #include "misc/vec/vecWec.h" |
| #include "misc/vec/vecQue.h" |
| #include "misc/vec/vecHsh.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes MFFCs of all qualifying nodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Gia_ObjCheckMffc_rec( Gia_Man_t * p,Gia_Obj_t * pObj, int Limit, Vec_Int_t * vNodes ) |
| { |
| int iFanin; |
| if ( Gia_ObjIsCi(pObj) ) |
| return 1; |
| assert( Gia_ObjIsAnd(pObj) ); |
| iFanin = Gia_ObjFaninId0p(p, pObj); |
| Vec_IntPush( vNodes, iFanin ); |
| if ( !Gia_ObjRefDecId(p, iFanin) && (Vec_IntSize(vNodes) > Limit || !Gia_ObjCheckMffc_rec(p, Gia_ObjFanin0(pObj), Limit, vNodes)) ) |
| return 0; |
| iFanin = Gia_ObjFaninId1p(p, pObj); |
| Vec_IntPush( vNodes, iFanin ); |
| if ( !Gia_ObjRefDecId(p, iFanin) && (Vec_IntSize(vNodes) > Limit || !Gia_ObjCheckMffc_rec(p, Gia_ObjFanin1(pObj), Limit, vNodes)) ) |
| return 0; |
| if ( !Gia_ObjIsMux(p, pObj) ) |
| return 1; |
| iFanin = Gia_ObjFaninId2p(p, pObj); |
| Vec_IntPush( vNodes, iFanin ); |
| if ( !Gia_ObjRefDecId(p, iFanin) && (Vec_IntSize(vNodes) > Limit || !Gia_ObjCheckMffc_rec(p, Gia_ObjFanin2(p, pObj), Limit, vNodes)) ) |
| return 0; |
| return 1; |
| } |
| static inline int Gia_ObjCheckMffc( Gia_Man_t * p, Gia_Obj_t * pRoot, int Limit, Vec_Int_t * vNodes, Vec_Int_t * vLeaves, Vec_Int_t * vInners ) |
| { |
| int RetValue, iObj, i; |
| Vec_IntClear( vNodes ); |
| RetValue = Gia_ObjCheckMffc_rec( p, pRoot, Limit, vNodes ); |
| if ( RetValue ) |
| { |
| Vec_IntClear( vLeaves ); |
| Vec_IntClear( vInners ); |
| Vec_IntSort( vNodes, 0 ); |
| Vec_IntForEachEntry( vNodes, iObj, i ) |
| if ( Gia_ObjRefNumId(p, iObj) > 0 || Gia_ObjIsCi(Gia_ManObj(p, iObj)) ) |
| { |
| if ( !Vec_IntSize(vLeaves) || Vec_IntEntryLast(vLeaves) != iObj ) |
| Vec_IntPush( vLeaves, iObj ); |
| } |
| else |
| { |
| if ( !Vec_IntSize(vInners) || Vec_IntEntryLast(vInners) != iObj ) |
| Vec_IntPush( vInners, iObj ); |
| } |
| Vec_IntPush( vInners, Gia_ObjId(p, pRoot) ); |
| } |
| Vec_IntForEachEntry( vNodes, iObj, i ) |
| Gia_ObjRefIncId( p, iObj ); |
| return RetValue; |
| } |
| Vec_Wec_t * Gia_ManComputeMffcs( Gia_Man_t * p, int LimitMin, int LimitMax, int SuppMax, int RatioBest ) |
| { |
| Gia_Obj_t * pObj; |
| Vec_Wec_t * vMffcs; |
| Vec_Int_t * vNodes, * vLeaves, * vInners, * vMffc; |
| int i, iPivot; |
| assert( p->pMuxes ); |
| vNodes = Vec_IntAlloc( 2 * LimitMax ); |
| vLeaves = Vec_IntAlloc( 2 * LimitMax ); |
| vInners = Vec_IntAlloc( 2 * LimitMax ); |
| vMffcs = Vec_WecAlloc( 1000 ); |
| Gia_ManCreateRefs( p ); |
| Gia_ManForEachAnd( p, pObj, i ) |
| { |
| if ( !Gia_ObjRefNum(p, pObj) ) |
| continue; |
| if ( !Gia_ObjCheckMffc(p, pObj, LimitMax, vNodes, vLeaves, vInners) ) |
| continue; |
| if ( Vec_IntSize(vInners) < LimitMin ) |
| continue; |
| if ( Vec_IntSize(vLeaves) > SuppMax ) |
| continue; |
| // improve cut |
| // collect cut |
| vMffc = Vec_WecPushLevel( vMffcs ); |
| Vec_IntGrow( vMffc, Vec_IntSize(vLeaves) + Vec_IntSize(vInners) + 20 ); |
| Vec_IntPush( vMffc, i ); |
| Vec_IntPush( vMffc, Vec_IntSize(vLeaves) ); |
| Vec_IntPush( vMffc, Vec_IntSize(vInners) ); |
| Vec_IntAppend( vMffc, vLeaves ); |
| // Vec_IntAppend( vMffc, vInners ); |
| // add last entry equal to the ratio |
| Vec_IntPush( vMffc, 1000 * Vec_IntSize(vInners) / Vec_IntSize(vLeaves) ); |
| } |
| Vec_IntFree( vNodes ); |
| Vec_IntFree( vLeaves ); |
| Vec_IntFree( vInners ); |
| // sort MFFCs by their inner/leaf ratio |
| Vec_WecSortByLastInt( vMffcs, 1 ); |
| Vec_WecForEachLevel( vMffcs, vMffc, i ) |
| Vec_IntPop( vMffc ); |
| // remove those whose ratio is not good |
| iPivot = RatioBest * Vec_WecSize(vMffcs) / 100; |
| Vec_WecForEachLevelStart( vMffcs, vMffc, i, iPivot ) |
| Vec_IntErase( vMffc ); |
| assert( iPivot <= Vec_WecSize(vMffcs) ); |
| Vec_WecShrink( vMffcs, iPivot ); |
| return vMffcs; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Gia_ManPrintDivStats( Gia_Man_t * p, Vec_Wec_t * vMffcs, Vec_Wec_t * vPivots ) |
| { |
| int fVerbose = 0; |
| Vec_Int_t * vMffc; |
| int i, nDivs, nDivsAll = 0, nDivs0 = 0; |
| Vec_WecForEachLevel( vMffcs, vMffc, i ) |
| { |
| nDivs = Vec_IntSize(vMffc) - 3 - Vec_IntEntry(vMffc, 1) - Vec_IntEntry(vMffc, 2); |
| nDivs0 += (nDivs == 0); |
| nDivsAll += nDivs; |
| if ( !fVerbose ) |
| continue; |
| printf( "%6d : ", Vec_IntEntry(vMffc, 0) ); |
| printf( "Leaf =%3d ", Vec_IntEntry(vMffc, 1) ); |
| printf( "Mffc =%4d ", Vec_IntEntry(vMffc, 2) ); |
| printf( "Divs =%4d ", nDivs ); |
| printf( "\n" ); |
| } |
| printf( "Collected %d (%.1f %%) MFFCs and %d (%.1f %%) have no divisors (div ave for others is %.2f).\n", |
| Vec_WecSize(vMffcs), 100.0 * Vec_WecSize(vMffcs) / Gia_ManAndNum(p), |
| nDivs0, 100.0 * nDivs0 / Gia_ManAndNum(p), |
| 1.0*nDivsAll/Abc_MaxInt(1, Vec_WecSize(vMffcs) - nDivs0) ); |
| printf( "Using %.2f MB for MFFCs and %.2f MB for pivots. ", |
| Vec_WecMemory(vMffcs)/(1<<20), Vec_WecMemory(vPivots)/(1<<20) ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compute divisors and Boolean functions for the nodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Gia_ManAddDivisors( Gia_Man_t * p, Vec_Wec_t * vMffcs ) |
| { |
| Vec_Wec_t * vPivots; |
| Vec_Int_t * vMffc, * vPivot, * vPivot0, * vPivot1; |
| Vec_Int_t * vCommon, * vCommon2, * vMap; |
| Gia_Obj_t * pObj; |
| int i, k, iObj, iPivot, iMffc; |
| //abctime clkStart = Abc_Clock(); |
| // initialize pivots (mapping of nodes into MFFCs whose leaves they are) |
| vMap = Vec_IntStartFull( Gia_ManObjNum(p) ); |
| vPivots = Vec_WecStart( Gia_ManObjNum(p) ); |
| Vec_WecForEachLevel( vMffcs, vMffc, i ) |
| { |
| assert( Vec_IntSize(vMffc) == 3 + Vec_IntEntry(vMffc, 1) ); |
| iPivot = Vec_IntEntry( vMffc, 0 ); |
| Vec_IntWriteEntry( vMap, iPivot, i ); |
| // iterate through the MFFC leaves |
| Vec_IntForEachEntryStart( vMffc, iObj, k, 3 ) |
| { |
| vPivot = Vec_WecEntry( vPivots, iObj ); |
| if ( Vec_IntSize(vPivot) == 0 ) |
| Vec_IntGrow(vPivot, 4); |
| Vec_IntPush( vPivot, iPivot ); |
| } |
| } |
| Vec_WecForEachLevel( vPivots, vPivot, i ) |
| Vec_IntSort( vPivot, 0 ); |
| // create pivots for internal nodes while growing MFFCs |
| vCommon = Vec_IntAlloc( 100 ); |
| vCommon2 = Vec_IntAlloc( 100 ); |
| Gia_ManForEachAnd( p, pObj, i ) |
| { |
| // find commont pivots |
| // the slow down happens because some PIs have very large sets of pivots |
| vPivot0 = Vec_WecEntry( vPivots, Gia_ObjFaninId0(pObj, i) ); |
| vPivot1 = Vec_WecEntry( vPivots, Gia_ObjFaninId1(pObj, i) ); |
| Vec_IntTwoFindCommon( vPivot0, vPivot1, vCommon ); |
| if ( Gia_ObjIsMuxId(p, i) ) |
| { |
| vPivot = Vec_WecEntry( vPivots, Gia_ObjFaninId2(p, i) ); |
| Vec_IntTwoFindCommon( vPivot, vCommon, vCommon2 ); |
| ABC_SWAP( Vec_Int_t *, vCommon, vCommon2 ); |
| } |
| if ( Vec_IntSize(vCommon) == 0 ) |
| continue; |
| // add new pivots (this trick increased memory used in vPivots) |
| vPivot = Vec_WecEntry( vPivots, i ); |
| Vec_IntTwoMerge2( vPivot, vCommon, vCommon2 ); |
| ABC_SWAP( Vec_Int_t, *vPivot, *vCommon2 ); |
| // grow MFFCs |
| Vec_IntForEachEntry( vCommon, iObj, k ) |
| { |
| iMffc = Vec_IntEntry( vMap, iObj ); |
| assert( iMffc != -1 ); |
| vMffc = Vec_WecEntry( vMffcs, iMffc ); |
| Vec_IntPush( vMffc, i ); |
| } |
| } |
| //Abc_PrintTime( 1, "Time", Abc_Clock() - clkStart ); |
| Vec_IntFree( vCommon ); |
| Vec_IntFree( vCommon2 ); |
| Vec_IntFree( vMap ); |
| Gia_ManPrintDivStats( p, vMffcs, vPivots ); |
| Vec_WecFree( vPivots ); |
| // returns the modified array of MFFCs |
| } |
| void Gia_ManResubTest( Gia_Man_t * p ) |
| { |
| Vec_Wec_t * vMffcs; |
| Gia_Man_t * pNew = Gia_ManDupMuxes( p, 2 ); |
| abctime clkStart = Abc_Clock(); |
| vMffcs = Gia_ManComputeMffcs( pNew, 4, 100, 8, 100 ); |
| Gia_ManAddDivisors( pNew, vMffcs ); |
| Vec_WecFree( vMffcs ); |
| Abc_PrintTime( 1, "Time", Abc_Clock() - clkStart ); |
| Gia_ManStop( pNew ); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Perform resubstitution.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
