diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2013-05-30 14:09:50 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2013-05-30 14:09:50 -0700 |
commit | 3c978925146b3be8ce6d3bca50a4462839b8d9fa (patch) | |
tree | 402d19b5b231906d305676e2c681e031d914a6eb /src/opt/sfm/sfmWin.c | |
parent | 67127b838d935876a879b1ced82f45de8e47621f (diff) | |
download | abc-3c978925146b3be8ce6d3bca50a4462839b8d9fa.tar.gz abc-3c978925146b3be8ce6d3bca50a4462839b8d9fa.tar.bz2 abc-3c978925146b3be8ce6d3bca50a4462839b8d9fa.zip |
New MFS package.
Diffstat (limited to 'src/opt/sfm/sfmWin.c')
-rw-r--r-- | src/opt/sfm/sfmWin.c | 155 |
1 files changed, 108 insertions, 47 deletions
diff --git a/src/opt/sfm/sfmWin.c b/src/opt/sfm/sfmWin.c index 9f3617d1..29b9d8e1 100644 --- a/src/opt/sfm/sfmWin.c +++ b/src/opt/sfm/sfmWin.c @@ -114,6 +114,7 @@ int Sfm_ObjMffcSize( Sfm_Ntk_t * p, int iObj ) static inline void Sfm_NtkIncrementTravId( Sfm_Ntk_t * p ) { p->nTravIds++; } static inline void Sfm_ObjSetTravIdCurrent( Sfm_Ntk_t * p, int Id ) { Vec_IntWriteEntry( &p->vTravIds, Id, p->nTravIds ); } static inline int Sfm_ObjIsTravIdCurrent( Sfm_Ntk_t * p, int Id ) { return (Vec_IntEntry(&p->vTravIds, Id) == p->nTravIds); } +static inline int Sfm_ObjIsTravIdPrevious( Sfm_Ntk_t * p, int Id ) { return (Vec_IntEntry(&p->vTravIds, Id) == p->nTravIds-1); } static inline void Sfm_NtkIncrementTravId2( Sfm_Ntk_t * p ) { p->nTravIds2++; } static inline void Sfm_ObjSetTravIdCurrent2( Sfm_Ntk_t * p, int Id ) { Vec_IntWriteEntry( &p->vTravIds2, Id, p->nTravIds2 ); } @@ -136,7 +137,8 @@ int Sfm_NtkCheckOverlap_rec( Sfm_Ntk_t * p, int iThis, int iNode ) int i, iFanin; if ( Sfm_ObjIsTravIdCurrent2(p, iThis) || iThis == iNode ) return 0; - if ( Sfm_ObjIsTravIdCurrent(p, iThis) ) +// if ( Sfm_ObjIsTravIdCurrent(p, iThis) ) + if ( Sfm_ObjIsTravIdPrevious(p, iThis) ) return 1; Sfm_ObjSetTravIdCurrent2(p, iThis); Sfm_ObjForEachFanin( p, iThis, iFanin, i ) @@ -152,24 +154,44 @@ int Sfm_NtkCheckOverlap( Sfm_Ntk_t * p, int iFan, int iNode ) /**Function************************************************************* - Synopsis [Check fanouts of the node.] + Synopsis [Recursively collects roots of the window.] - Description [Returns 1 if they can be used instead of the node.] + Description [] SideEffects [] SeeAlso [] ***********************************************************************/ -int Sfm_NtkCheckFanouts( Sfm_Ntk_t * p, int iNode ) +static inline int Sfm_NtkCheckRoot( Sfm_Ntk_t * p, int iNode, int nLevelMax ) { int i, iFanout; - if ( Sfm_ObjFanoutNum(p, iNode) >= p->pPars->nFanoutMax ) - return 0; + // the node is the root if one of the following is true: + // (1) the node has more than fanouts than the limit + if ( Sfm_ObjFanoutNum(p, iNode) > p->pPars->nFanoutMax ) + return 1; + // (2) the node has CO fanouts + // (3) the node has fanouts above the cutoff level Sfm_ObjForEachFanout( p, iNode, iFanout, i ) - if ( !Sfm_NtkCheckOverlap( p, iFanout, iNode ) ) - return 0; - return 1; + if ( Sfm_ObjIsPo(p, iFanout) || Sfm_ObjLevel(p, iFanout) > nLevelMax )//|| !Sfm_NtkCheckOverlap(p, iFanout, iNode) ) + return 1; + return 0; +} +void Sfm_NtkComputeRoots_rec( Sfm_Ntk_t * p, int iNode, int nLevelMax, Vec_Int_t * vRoots, Vec_Int_t * vTfo ) +{ + int i, iFanout; + assert( Sfm_ObjIsNode(p, iNode) ); + if ( Sfm_ObjIsTravIdCurrent(p, iNode) ) + return; + Sfm_ObjSetTravIdCurrent(p, iNode); + if ( iNode != p->iPivotNode ) + Vec_IntPush( vTfo, iNode ); + // check if the node should be the root + if ( Sfm_NtkCheckRoot( p, iNode, nLevelMax ) ) + Vec_IntPush( vRoots, iNode ); + else // if not, explore its fanouts + Sfm_ObjForEachFanout( p, iNode, iFanout, i ) + Sfm_NtkComputeRoots_rec( p, iFanout, nLevelMax, vRoots, vTfo ); } /**Function************************************************************* @@ -244,7 +266,7 @@ static inline int Sfm_ObjIsUseful( Sfm_Ntk_t * p, int iNode ) SeeAlso [] ***********************************************************************/ -int Sfm_NtkCollectTfi_rec( Sfm_Ntk_t * p, int iNode, int nWinSizeMax ) +int Sfm_NtkCollectTfi_rec( Sfm_Ntk_t * p, int iNode, Vec_Int_t * vLeaves, Vec_Int_t * vNodes ) { int i, iFanin; if ( Sfm_ObjIsTravIdCurrent( p, iNode ) ) @@ -252,50 +274,41 @@ int Sfm_NtkCollectTfi_rec( Sfm_Ntk_t * p, int iNode, int nWinSizeMax ) Sfm_ObjSetTravIdCurrent( p, iNode ); if ( Sfm_ObjIsPi( p, iNode ) ) { - Vec_IntPush( p->vLeaves, iNode ); + Vec_IntPush( vLeaves, iNode ); return 0; } Sfm_ObjForEachFanin( p, iNode, iFanin, i ) - if ( Sfm_NtkCollectTfi_rec( p, iFanin, nWinSizeMax ) ) + if ( Sfm_NtkCollectTfi_rec( p, iFanin, vLeaves, vNodes ) ) return 1; - Vec_IntPush( p->vNodes, iNode ); - return nWinSizeMax && (Vec_IntSize(p->vNodes) > nWinSizeMax); + Vec_IntPush( vNodes, iNode ); + return p->pPars->nWinSizeMax && (Vec_IntSize(vNodes) > p->pPars->nWinSizeMax); } int Sfm_NtkCreateWindow( Sfm_Ntk_t * p, int iNode, int fVerbose ) { int i, k, iTemp, nDivStart; - abctime clk = Abc_Clock(); + abctime clkDiv, clkWin = Abc_Clock(); + assert( Sfm_ObjIsNode( p, iNode ) ); + p->iPivotNode = iNode; Vec_IntClear( p->vLeaves ); // leaves + Vec_IntClear( p->vLeaves2 );// leaves Vec_IntClear( p->vNodes ); // internal + Vec_IntClear( p->vNodes2 ); // internal Vec_IntClear( p->vDivs ); // divisors Vec_IntClear( p->vRoots ); // roots Vec_IntClear( p->vTfo ); // roots + // collect transitive fanin Sfm_NtkIncrementTravId( p ); - if ( Sfm_NtkCollectTfi_rec( p, iNode, p->pPars->nWinSizeMax ) ) + if ( Sfm_NtkCollectTfi_rec( p, iNode, p->vLeaves, p->vNodes ) ) { p->nMaxDivs++; - p->timeWin += Abc_Clock() - clk; + p->timeWin += Abc_Clock() - clkWin; return 0; } - // collect TFO (currently use only one level of TFO) -// if ( Sfm_NtkCheckFanouts(p, iNode) ) - if ( 0 ) - { - Sfm_ObjForEachFanout( p, iNode, iTemp, i ) - { - if ( Sfm_ObjIsPo(p, iTemp) ) - continue; - Vec_IntPush( p->vRoots, iTemp ); - Vec_IntPush( p->vTfo, iTemp ); - } - } - else - Vec_IntPush( p->vRoots, iNode ); - p->timeWin += Abc_Clock() - clk; - clk = Abc_Clock(); + // create divisors + clkDiv = Abc_Clock(); Vec_IntClear( p->vDivs ); Vec_IntForEachEntry( p->vLeaves, iTemp, i ) Vec_IntPush( p->vDivs, iTemp ); @@ -304,26 +317,26 @@ int Sfm_NtkCreateWindow( Sfm_Ntk_t * p, int iNode, int fVerbose ) Vec_IntPop( p->vDivs ); // add non-topological divisors nDivStart = Vec_IntSize(p->vDivs); - if ( Vec_IntSize(p->vDivs) < p->pPars->nWinSizeMax ) + if ( Vec_IntSize(p->vDivs) < p->pPars->nWinSizeMax + 0 ) { Sfm_NtkIncrementTravId2( p ); Vec_IntForEachEntry( p->vDivs, iTemp, i ) - if ( Vec_IntSize(p->vDivs) < p->pPars->nWinSizeMax ) + if ( Vec_IntSize(p->vDivs) < p->pPars->nWinSizeMax + 0 ) Sfm_NtkAddDivisors( p, iTemp, Sfm_ObjLevel(p, iNode) ); } if ( Vec_IntSize(p->vDivs) > p->pPars->nWinSizeMax ) + { +/* + k = 0; + Vec_IntForEachEntryStart( p->vDivs, iTemp, i, Vec_IntSize(p->vDivs) - p->pPars->nWinSizeMax ) + Vec_IntWriteEntry( p->vDivs, k++, iTemp ); + assert( k == p->pPars->nWinSizeMax ); +*/ Vec_IntShrink( p->vDivs, p->pPars->nWinSizeMax ); + } assert( Vec_IntSize(p->vDivs) <= p->pPars->nWinSizeMax ); - p->nMaxDivs += (Vec_IntSize(p->vDivs) == p->pPars->nWinSizeMax); - // create ordering of the nodes - Vec_IntClear( p->vOrder ); - Vec_IntForEachEntryReverse( p->vNodes, iTemp, i ) - Vec_IntPush( p->vOrder, iTemp ); - Vec_IntForEachEntry( p->vLeaves, iTemp, i ) - Vec_IntPush( p->vOrder, iTemp ); - Vec_IntForEachEntryStart( p->vDivs, iTemp, i, nDivStart ) - Vec_IntPush( p->vOrder, iTemp ); - // remove fanins from divisors + p->nMaxDivs += (int)(Vec_IntSize(p->vDivs) == p->pPars->nWinSizeMax); + // remove node/fanins from divisors // mark fanins Sfm_NtkIncrementTravId2( p ); Sfm_ObjSetTravIdCurrent2( p, iNode ); @@ -336,9 +349,57 @@ int Sfm_NtkCreateWindow( Sfm_Ntk_t * p, int iNode, int fVerbose ) Vec_IntWriteEntry( p->vDivs, k++, iTemp ); Vec_IntShrink( p->vDivs, k ); assert( Vec_IntSize(p->vDivs) <= p->pPars->nWinSizeMax ); - // statistics + clkDiv = Abc_Clock() - clkDiv; + p->timeDiv += clkDiv; p->nTotalDivs += Vec_IntSize(p->vDivs); - p->timeDiv += Abc_Clock() - clk; + + // collect TFO and window roots + if ( p->pPars->nTfoLevMax > 0 && !Sfm_NtkCheckRoot(p, iNode, Sfm_ObjLevel(p, iNode) + p->pPars->nTfoLevMax) ) + { + // explore transitive fanout + Sfm_NtkIncrementTravId( p ); + Sfm_NtkComputeRoots_rec( p, iNode, Sfm_ObjLevel(p, iNode) + p->pPars->nTfoLevMax, p->vRoots, p->vTfo ); + assert( Vec_IntSize(p->vRoots) > 0 ); + assert( Vec_IntSize(p->vTfo) > 0 ); + // compute new leaves and nodes + Sfm_NtkIncrementTravId( p ); + Vec_IntForEachEntry( p->vRoots, iTemp, i ) + if ( Sfm_NtkCollectTfi_rec( p, iTemp, p->vLeaves2, p->vNodes2 ) ) + break; + if ( i == Vec_IntSize(p->vRoots) ) + { +// printf( "%d -> %d %d -> %d\n", Vec_IntSize(p->vLeaves), Vec_IntSize(p->vLeaves2), Vec_IntSize(p->vNodes), Vec_IntSize(p->vNodes2) ); + // swap leaves and nodes + ABC_SWAP( Vec_Int_t *, p->vLeaves, p->vLeaves2 ); + ABC_SWAP( Vec_Int_t *, p->vNodes, p->vNodes2 ); + } + else + { + Vec_IntClear( p->vRoots ); + Vec_IntClear( p->vTfo ); + } +// printf( "Roots = %d. TFO = %d.\n", Vec_IntSize(p->vRoots), Vec_IntSize(p->vTfo) ); + } + + // create ordering of the nodes, leaves and divisors that are not among nodes/leaves + Vec_IntClear( p->vOrder ); + Sfm_NtkIncrementTravId2( p ); + Vec_IntForEachEntryReverse( p->vNodes, iTemp, i ) + { + Sfm_ObjSetTravIdCurrent2( p, iTemp ); + Vec_IntPush( p->vOrder, iTemp ); + } + Vec_IntForEachEntry( p->vLeaves, iTemp, i ) + { + Sfm_ObjSetTravIdCurrent2( p, iTemp ); + Vec_IntPush( p->vOrder, iTemp ); + } + Vec_IntForEachEntry( p->vDivs, iTemp, i ) + if ( !Sfm_ObjIsTravIdCurrent2(p, iTemp) ) + Vec_IntPush( p->vOrder, iTemp ); + + // statistics + p->timeWin += Abc_Clock() - clkWin - clkDiv; if ( !fVerbose ) return 1; |