diff options
Diffstat (limited to 'src/map/if')
-rw-r--r-- | src/map/if/if.h | 15 | ||||
-rw-r--r-- | src/map/if/ifMan.c | 4 | ||||
-rw-r--r-- | src/map/if/ifMap.c | 30 | ||||
-rw-r--r-- | src/map/if/ifTruth.c | 199 | ||||
-rw-r--r-- | src/map/if/ifUtil.c | 84 |
5 files changed, 307 insertions, 25 deletions
diff --git a/src/map/if/if.h b/src/map/if/if.h index f74a59da..9e649e0c 100644 --- a/src/map/if/if.h +++ b/src/map/if/if.h @@ -333,7 +333,7 @@ static inline void * If_ObjCopy( If_Obj_t * pObj ) { r static inline int If_ObjLevel( If_Obj_t * pObj ) { return pObj->Level; } static inline void If_ObjSetLevel( If_Obj_t * pObj, int Level ) { pObj->Level = Level; } static inline void If_ObjSetCopy( If_Obj_t * pObj, void * pCopy ) { pObj->pCopy = pCopy; } -static inline void If_ObjSetChoice( If_Obj_t * pObj, If_Obj_t * pEqu ) { pObj->pEquiv = pEqu; } +static inline void If_ObjSetChoice( If_Obj_t * pObj, If_Obj_t * pEqu ) { assert( pObj->Id > pEqu->Id ); pObj->pEquiv = pEqu; } static inline If_Cut_t * If_ObjCutBest( If_Obj_t * pObj ) { return &pObj->CutBest; } static inline unsigned If_ObjCutSign( unsigned ObjId ) { return (1 << (ObjId % 31)); } @@ -353,8 +353,9 @@ static inline void If_CutSetDataInt( If_Cut_t * pCut, int Data ) { * static inline int If_CutLeaveNum( If_Cut_t * pCut ) { return pCut->nLeaves; } static inline int * If_CutLeaves( If_Cut_t * pCut ) { return pCut->pLeaves; } static inline unsigned * If_CutTruth( If_Cut_t * pCut ) { return pCut->pTruth; } +static inline word * If_CutTruthW( If_Cut_t * pCut ) { return (word *)pCut->pTruth; } static inline unsigned If_CutSuppMask( If_Cut_t * pCut ) { return (~(unsigned)0) >> (32-pCut->nLeaves); } -static inline int If_CutTruthWords( int nVarsMax ) { return nVarsMax <= 5 ? 1 : (1 << (nVarsMax - 5)); } +static inline int If_CutTruthWords( int nVarsMax ) { return nVarsMax <= 5 ? 2 : (1 << (nVarsMax - 5)); } static inline int If_CutPermWords( int nVarsMax ) { return nVarsMax / sizeof(int) + ((nVarsMax % sizeof(int)) > 0); } static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { return pCut->fUser? (float)pCut->Cost : (p->pPars->pLutLib? p->pPars->pLutLib->pLutAreas[pCut->nLeaves] : (float)1.0); } @@ -505,8 +506,9 @@ extern void If_CutPropagateRequired( If_Man_t * p, If_Obj_t * pObj, I extern void If_CutRotatePins( If_Man_t * p, If_Cut_t * pCut ); /*=== ifTruth.c ===========================================================*/ extern int If_CutTruthMinimize( If_Man_t * p, If_Cut_t * pCut ); -extern int If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 ); extern void If_CutTruthPermute( unsigned * pOut, unsigned * pIn, int nVars, float * pDelays, int * pVars ); +extern int If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 ); +extern int If_CutComputeTruth2( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 ); /*=== ifUtil.c ============================================================*/ extern void If_ManCleanNodeCopy( If_Man_t * p ); extern void If_ManCleanCutData( If_Man_t * p ); @@ -525,13 +527,18 @@ extern Vec_Ptr_t * If_ManCollectMappingDirect( If_Man_t * p ); extern Vec_Int_t * If_ManCollectMappingInt( If_Man_t * p ); extern int If_ManCountSpecialPos( If_Man_t * p ); +extern void If_CutTraverse( If_Man_t * p, If_Obj_t * pRoot, If_Cut_t * pCut, Vec_Ptr_t * vNodes ); +extern void If_ObjPrint( If_Obj_t * pObj ); /*=== abcRec.c ============================================================*/ +/*=== abcRec2.c ============================================================*/ +/*=== abcRec3.c ============================================================*/ extern int If_CutDelayRecCost(If_Man_t* p, If_Cut_t* pCut, If_Obj_t * pObj); extern int If_CutDelayRecCost2(If_Man_t* p, If_Cut_t* pCut, If_Obj_t * pObj); -/*=== abcRec2.c ============================================================*/ +extern int If_CutDelayRecCost3(If_Man_t* p, If_Cut_t* pCut, If_Obj_t * pObj); extern ABC_DLL int Abc_NtkRecIsRunning(); extern ABC_DLL int Abc_NtkRecIsRunning2(); +extern ABC_DLL int Abc_NtkRecIsRunning3(); // othe packages extern int Bat_ManCellFuncLookup( unsigned * pTruth, int nVars, int nLeaves ); diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c index 3028e370..0ebdec1b 100644 --- a/src/map/if/ifMan.c +++ b/src/map/if/ifMan.c @@ -337,6 +337,7 @@ void If_ManCreateChoice( If_Man_t * p, If_Obj_t * pObj ) // mark the largest level if ( p->nLevelMax < (int)pObj->Level ) p->nLevelMax = (int)pObj->Level; + p->nChoices++; } /**Function************************************************************* @@ -410,8 +411,7 @@ void If_ManSetupCutTriv( If_Man_t * p, If_Cut_t * pCut, int ObjId ) // set up elementary truth table of the unit cut if ( p->pPars->fTruth ) { - int i, nTruthWords; - nTruthWords = pCut->nLimit <= 5 ? 1 : (1 << (pCut->nLimit - 5)); + int i, nTruthWords = If_CutTruthWords(pCut->nLimit); for ( i = 0; i < nTruthWords; i++ ) If_CutTruth(pCut)[i] = 0xAAAAAAAA; } diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c index 6fcb8799..1f7ba898 100644 --- a/src/map/if/ifMap.c +++ b/src/map/if/ifMap.c @@ -75,7 +75,8 @@ float If_CutDelaySpecial( If_Man_t * p, If_Cut_t * pCut, int fCarry ) Delay = IF_MAX( Delay, Pin2Pin[fCarry][i] + DelayCur ); } return Delay; - } +} + /**Function************************************************************* @@ -157,12 +158,13 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep /// pCut->Delay = If_CutDelayLutStruct( p, pCut, p->pPars->pLutStruct, p->pPars->WireDelay ); if ( p->pPars->fUserRecLib ) { - if((Abc_NtkRecIsRunning2()&& Abc_NtkRecIsRunning()) || (!Abc_NtkRecIsRunning2()&& !Abc_NtkRecIsRunning())) - assert(0); - else if(Abc_NtkRecIsRunning()) - pCut->Delay = If_CutDelayRecCost(p, pCut, pObj); + assert( Abc_NtkRecIsRunning() + Abc_NtkRecIsRunning2() + Abc_NtkRecIsRunning3() == 1 ); + if ( Abc_NtkRecIsRunning3() ) + pCut->Delay = If_CutDelayRecCost3(p, pCut, pObj); + else if( Abc_NtkRecIsRunning2() ) + pCut->Delay = If_CutDelayRecCost2(p, pCut, pObj); else - pCut->Delay = If_CutDelayRecCost2(p, pCut, pObj); + pCut->Delay = If_CutDelayRecCost(p, pCut, pObj); } else if(p->pPars->fDelayOpt) pCut->Delay = If_CutDelaySopCost(p,pCut); @@ -211,8 +213,10 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep if ( p->pPars->fTruth ) { // clock_t clk = clock(); - int RetValue = If_CutComputeTruth( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 ); +// int RetValue = If_CutComputeTruth( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 ); + int RetValue = If_CutComputeTruth2( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 ); // p->timeTruth += clock() - clk; + pCut->fUseless = 0; if ( p->pPars->pFuncCell && RetValue < 2 ) { @@ -236,12 +240,13 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep /// pCut->Delay = If_CutDelayLutStruct( p, pCut, p->pPars->pLutStruct, p->pPars->WireDelay ); if ( p->pPars->fUserRecLib ) { - if((Abc_NtkRecIsRunning2()&& Abc_NtkRecIsRunning()) || (!Abc_NtkRecIsRunning2()&& !Abc_NtkRecIsRunning())) - assert(0); - else if(Abc_NtkRecIsRunning()) - pCut->Delay = If_CutDelayRecCost(p, pCut, pObj); - else + assert( Abc_NtkRecIsRunning() + Abc_NtkRecIsRunning2() + Abc_NtkRecIsRunning3() == 1 ); + if ( Abc_NtkRecIsRunning3() ) + pCut->Delay = If_CutDelayRecCost3(p, pCut, pObj); + else if( Abc_NtkRecIsRunning2() ) pCut->Delay = If_CutDelayRecCost2(p, pCut, pObj); + else + pCut->Delay = If_CutDelayRecCost(p, pCut, pObj); } else if (p->pPars->fDelayOpt) pCut->Delay = If_CutDelaySopCost(p, pCut); @@ -263,6 +268,7 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep pCut->AveRefs = (Mode == 0)? (float)0.0 : If_CutAverageRefs( p, pCut ); // insert the cut into storage If_CutSort( p, pCutSet, pCut ); +// If_CutTraverse( p, pObj, pCut ); } assert( pCutSet->nCuts > 0 ); diff --git a/src/map/if/ifTruth.c b/src/map/if/ifTruth.c index f0289695..4b0db8b4 100644 --- a/src/map/if/ifTruth.c +++ b/src/map/if/ifTruth.c @@ -19,6 +19,7 @@ ***********************************************************************/ #include "if.h" +#include "misc/util/utilTruth.h" ABC_NAMESPACE_IMPL_START @@ -43,29 +44,28 @@ ABC_NAMESPACE_IMPL_START SeeAlso [] ***********************************************************************/ -static inline int If_TruthWordNum( int nVars ) { return nVars <= 5 ? 1 : (1 << (nVars - 5)); } static inline void If_TruthNot( unsigned * pOut, unsigned * pIn, int nVars ) { int w; - for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- ) + for ( w = If_CutTruthWords(nVars)-1; w >= 0; w-- ) pOut[w] = ~pIn[w]; } static inline void If_TruthCopy( unsigned * pOut, unsigned * pIn, int nVars ) { int w; - for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- ) + for ( w = If_CutTruthWords(nVars)-1; w >= 0; w-- ) pOut[w] = pIn[w]; } static inline void If_TruthNand( unsigned * pOut, unsigned * pIn0, unsigned * pIn1, int nVars ) { int w; - for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- ) + for ( w = If_CutTruthWords(nVars)-1; w >= 0; w-- ) pOut[w] = ~(pIn0[w] & pIn1[w]); } static inline void If_TruthAnd( unsigned * pOut, unsigned * pIn0, unsigned * pIn1, int nVars ) { int w; - for ( w = If_TruthWordNum(nVars)-1; w >= 0; w-- ) + for ( w = If_CutTruthWords(nVars)-1; w >= 0; w-- ) pOut[w] = pIn0[w] & pIn1[w]; } @@ -89,7 +89,7 @@ void If_TruthSwapAdjacentVars( unsigned * pOut, unsigned * pIn, int nVars, int i { 0xF00FF00F, 0x00F000F0, 0x0F000F00 }, { 0xFF0000FF, 0x0000FF00, 0x00FF0000 } }; - int nWords = If_TruthWordNum( nVars ); + int nWords = If_CutTruthWords( nVars ); int i, k, Step, Shift; assert( iVar < nVars - 1 ); @@ -245,7 +245,7 @@ void If_TruthShrink( unsigned * pOut, unsigned * pIn, int nVars, int nVarsAll, u ***********************************************************************/ int If_CutTruthVarInSupport( unsigned * pTruth, int nVars, int iVar ) { - int nWords = If_TruthWordNum( nVars ); + int nWords = If_CutTruthWords( nVars ); int i, k, Step; assert( iVar < nVars ); @@ -449,6 +449,191 @@ int If_CutTruthMinimize( If_Man_t * p, If_Cut_t * pCut ) } + + +/**Function************************************************************* + + Synopsis [Performs truth table computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_CutTruthMinimize6( If_Man_t * p, If_Cut_t * pCut ) +{ + unsigned uSupport; + int i, k, nSuppSize; + int nVars = If_CutLeaveNum(pCut); + // compute the support of the cut's function + uSupport = Abc_Tt6SupportAndSize( *If_CutTruthW(pCut), nVars, &nSuppSize ); + if ( nSuppSize == If_CutLeaveNum(pCut) ) + return 0; +// TEMPORARY + if ( nSuppSize < 2 ) + { + p->nSmallSupp++; + return 2; + } + // update leaves and signature + pCut->uSign = 0; + for ( i = k = 0; i < nVars; i++ ) + { + if ( !(uSupport & (1 << i)) ) + continue; + pCut->uSign |= If_ObjCutSign( pCut->pLeaves[i] ); + if ( k < i ) + { + pCut->pLeaves[k] = pCut->pLeaves[i]; + Abc_TtSwapVars( If_CutTruthW(pCut), pCut->nLimit, k, i ); + } + k++; + } + assert( k == nSuppSize ); + pCut->nLeaves = nSuppSize; + // verify the result +// assert( nSuppSize == Abc_TtSupportSize(If_CutTruthW(pCut), nVars) ); + return 1; +} +static inline word If_TruthStretch6( word Truth, If_Cut_t * pCut, If_Cut_t * pCut0 ) +{ + int i, k; + for ( i = (int)pCut->nLeaves - 1, k = (int)pCut0->nLeaves - 1; i >= 0 && k >= 0; i-- ) + { + if ( pCut0->pLeaves[k] < pCut->pLeaves[i] ) + continue; + assert( pCut0->pLeaves[k] == pCut->pLeaves[i] ); + if ( k < i ) + Abc_TtSwapVars( &Truth, pCut->nLimit, k, i ); + k--; + } + return Truth; +} +static inline int If_CutComputeTruth6( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 ) +{ + word t0 = (fCompl0 ^ pCut0->fCompl) ? ~*If_CutTruthW(pCut0) : *If_CutTruthW(pCut0); + word t1 = (fCompl1 ^ pCut1->fCompl) ? ~*If_CutTruthW(pCut1) : *If_CutTruthW(pCut1); + assert( pCut->nLimit <= 6 ); + t0 = If_TruthStretch6( t0, pCut, pCut0 ); + t1 = If_TruthStretch6( t1, pCut, pCut1 ); + *If_CutTruthW(pCut) = t0 & t1; + if ( p->pPars->fCutMin ) + return If_CutTruthMinimize6( p, pCut ); + return 0; +} + + +/**Function************************************************************* + + Synopsis [Performs truth table computation.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +// this procedure handles special case reductions +static inline int If_CutTruthMinimize21( If_Man_t * p, If_Cut_t * pCut ) +{ + word * pTruth = If_CutTruthW(pCut); + int i, k, nVars = If_CutLeaveNum(pCut); + unsigned uSign = 0; + for ( i = k = 0; i < nVars; i++ ) + { + if ( !Abc_TtHasVar( pTruth, nVars, i ) ) + continue; + uSign |= If_ObjCutSign( pCut->pLeaves[i] ); + if ( k < i ) + { + pCut->pLeaves[k] = pCut->pLeaves[i]; + Abc_TtSwapVars( pTruth, nVars, k, i ); + } + k++; + } + if ( k == nVars ) + return 0; + assert( k < nVars ); + pCut->nLeaves = k; + pCut->uSign = uSign; +// TEMPORARY + if ( pCut->nLeaves < 2 ) + { + p->nSmallSupp++; + return 2; + } + // verify the result + assert( If_CutLeaveNum(pCut) == Abc_TtSupportSize(pTruth, nVars) ); + return 1; +} +static inline int If_CutTruthMinimize2( If_Man_t * p, If_Cut_t * pCut ) +{ + unsigned uSupport; + int i, k, nSuppSize; + int nVars = If_CutLeaveNum(pCut); + // compute the support of the cut's function + uSupport = Abc_TtSupportAndSize( If_CutTruthW(pCut), nVars, &nSuppSize ); + if ( nSuppSize == If_CutLeaveNum(pCut) ) + return 0; +// TEMPORARY + if ( nSuppSize < 2 ) + { + p->nSmallSupp++; + return 2; + } + // update leaves and signature + pCut->uSign = 0; + for ( i = k = 0; i < nVars; i++ ) + { + if ( !(uSupport & (1 << i)) ) + continue; + pCut->uSign |= If_ObjCutSign( pCut->pLeaves[i] ); + if ( k < i ) + { + pCut->pLeaves[k] = pCut->pLeaves[i]; + Abc_TtSwapVars( If_CutTruthW(pCut), pCut->nLimit, k, i ); + } + k++; + } + assert( k == nSuppSize ); + pCut->nLeaves = nSuppSize; + // verify the result +// assert( nSuppSize == Abc_TtSupportSize(If_CutTruthW(pCut), nVars) ); + return 1; +} +static inline void If_TruthStretch2( word * pTruth, If_Cut_t * pCut, If_Cut_t * pCut0 ) +{ + int i, k; + for ( i = (int)pCut->nLeaves - 1, k = (int)pCut0->nLeaves - 1; i >= 0 && k >= 0; i-- ) + { + if ( pCut0->pLeaves[k] < pCut->pLeaves[i] ) + continue; + assert( pCut0->pLeaves[k] == pCut->pLeaves[i] ); + if ( k < i ) + Abc_TtSwapVars( pTruth, pCut->nLimit, k, i ); + k--; + } +} +inline int If_CutComputeTruth2( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 ) +{ + int nWords; + if ( pCut->nLimit < 7 ) + return If_CutComputeTruth6( p, pCut, pCut0, pCut1, fCompl0, fCompl1 ); + nWords = Abc_TtWordNum( pCut->nLimit ); + Abc_TtCopy( (word *)p->puTemp[0], If_CutTruthW(pCut0), nWords, fCompl0 ^ pCut0->fCompl ); + Abc_TtCopy( (word *)p->puTemp[1], If_CutTruthW(pCut1), nWords, fCompl1 ^ pCut1->fCompl ); + If_TruthStretch2( (word *)p->puTemp[0], pCut, pCut0 ); + If_TruthStretch2( (word *)p->puTemp[1], pCut, pCut1 ); + Abc_TtAnd( If_CutTruthW(pCut), (word *)p->puTemp[0], (word *)p->puTemp[1], nWords, 0 ); + if ( p->pPars->fCutMin ) + return If_CutTruthMinimize2( p, pCut ); + return 0; +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/if/ifUtil.c b/src/map/if/ifUtil.c index 4d904613..b8b03d70 100644 --- a/src/map/if/ifUtil.c +++ b/src/map/if/ifUtil.c @@ -769,6 +769,90 @@ int If_ManCountSpecialPos( If_Man_t * p ) } +/**Function************************************************************* + + Synopsis [Traverse the cut and counts its volume.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static void If_CutTraverse_rec( If_Obj_t * pNode, Vec_Ptr_t * vNodes ) +{ + if ( pNode->fMark ) + return; + pNode->fMark = 1; +// assert( !If_ObjIsCi(pNode) ); // does not hold with cut minimization + if ( If_ObjIsAnd(pNode) ) + If_CutTraverse_rec( If_ObjFanin0(pNode), vNodes ); + if ( If_ObjIsAnd(pNode) ) + If_CutTraverse_rec( If_ObjFanin1(pNode), vNodes ); + Vec_PtrPush( vNodes, pNode ); +} +void If_CutTraverse( If_Man_t * p, If_Obj_t * pRoot, If_Cut_t * pCut, Vec_Ptr_t * vNodes ) +{ + If_Obj_t * pLeaf; + int i; + // collect the internal nodes of the cut + Vec_PtrClear( vNodes ); + If_CutForEachLeaf( p, pCut, pLeaf, i ) + { + Vec_PtrPush( vNodes, pLeaf ); + assert( pLeaf->fMark == 0 ); + pLeaf->fMark = 1; + } + // collect other nodes + If_CutTraverse_rec( pRoot, vNodes ); + // clean the mark + Vec_PtrForEachEntry( If_Obj_t *, vNodes, pLeaf, i ) + pLeaf->fMark = 0; +} +void If_CutTraverseTest( If_Man_t * p, If_Obj_t * pRoot, If_Cut_t * pCut ) +{ + Vec_Ptr_t * vNodes; + vNodes = Vec_PtrAlloc( 1000 ); + If_CutTraverse( p, pRoot, pCut, vNodes ); +//if ( Vec_PtrSize(vNodes) > 30 ) +//printf( "%d ", Vec_PtrSize(vNodes) ); + Vec_PtrFree( vNodes ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void If_ObjPrint( If_Obj_t * pObj ) +{ + if ( pObj == NULL ) + { + printf( "Object is NULL." ); + return; + } + printf( "Obj %4d : ", If_ObjId(pObj) ); + if ( If_ObjIsConst1(pObj) ) + printf( "constant 1" ); + else if ( If_ObjIsCi(pObj) ) + printf( "PI" ); + else if ( If_ObjIsCo(pObj) ) + printf( "PO( %4d%s )", If_ObjId(If_ObjFanin0(pObj)), (If_ObjFaninC0(pObj)? "\'" : " ") ); + else + printf( "AND( %4d%s, %4d%s )", + If_ObjId(If_ObjFanin0(pObj)), (If_ObjFaninC0(pObj)? "\'" : " "), + If_ObjId(If_ObjFanin1(pObj)), (If_ObjFaninC1(pObj)? "\'" : " ") ); + printf( " (refs = %3d)", pObj->nVisitsCopy ); + printf( "\n" ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |