From 2f926f2fafba8dc2ec073c51b5ac9fdabd9ad201 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 30 Mar 2014 12:07:49 -0700 Subject: Improving cut computation. --- src/map/if/if.h | 2 + src/map/if/ifCache.c | 6 +- src/map/if/ifCut.c | 419 +++++++++++++++++--------------------------------- src/map/if/ifMan.c | 21 +-- src/map/if/ifMap.c | 69 ++------- src/map/if/ifReduce.c | 120 +-------------- src/map/if/ifTruth.c | 19 +-- 7 files changed, 177 insertions(+), 479 deletions(-) (limited to 'src/map') diff --git a/src/map/if/if.h b/src/map/if/if.h index 320139a0..feb560f7 100644 --- a/src/map/if/if.h +++ b/src/map/if/if.h @@ -481,9 +481,11 @@ static inline void If_AndClear( If_And_t * pNode ) { * extern int If_ManPerformMapping( If_Man_t * p ); extern int If_ManPerformMappingComb( If_Man_t * p ); /*=== ifCut.c ============================================================*/ +extern int If_CutVerifyCuts( If_Set_t * pCutSet, int fOrdered ); extern int If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut ); extern void If_CutSort( If_Man_t * p, If_Set_t * pCutSet, If_Cut_t * pCut ); extern void If_CutOrder( If_Cut_t * pCut ); +extern int If_CutMergeOrdered( If_Man_t * p, If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut ); extern int If_CutMerge( If_Man_t * p, If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut ); extern int If_CutCheck( If_Cut_t * pCut ); extern void If_CutPrint( If_Cut_t * pCut ); diff --git a/src/map/if/ifCache.c b/src/map/if/ifCache.c index d0da8c18..f2312447 100644 --- a/src/map/if/ifCache.c +++ b/src/map/if/ifCache.c @@ -79,14 +79,14 @@ void If_ManCacheAnalize( If_Man_t * p ) { uUnique = Vec_IntCountUnique(vTest[i]); printf( "%2d-var entries = %8d. (%6.2f %%) Unique entries = %8d. (%6.2f %%)\n", - i, Vec_IntSize(vTest[i]), 100.0*Vec_IntSize(vTest[i])/Vec_IntSize(vRes), - uUnique, 100.0*uUnique/Vec_IntSize(vTest[i]) ); + i, Vec_IntSize(vTest[i]), 100.0*Vec_IntSize(vTest[i])/Abc_MaxInt(1, Vec_IntSize(vRes)), + uUnique, 100.0*uUnique/Abc_MaxInt(1, Vec_IntSize(vTest[i])) ); } for ( i = 0; i <= p->pPars->nLutSize; i++ ) Vec_IntFree( vTest[i] ); uUnique = Vec_IntCountUnique(vRes); printf( "Total entries = %8d. (%6.2f %%) Unique entries = %8d. (%6.2f %%)\n", - Vec_IntSize(p->vCutData)/4, 100.0, uUnique, 100.0*uUnique/(Vec_IntSize(p->vCutData)/4) ); + Vec_IntSize(p->vCutData)/4, 100.0, uUnique, 100.0*uUnique/Abc_MaxInt(1, Vec_IntSize(p->vCutData)/4) ); Vec_IntFree( vRes ); } diff --git a/src/map/if/ifCut.c b/src/map/if/ifCut.c index 65627dc2..5b520102 100644 --- a/src/map/if/ifCut.c +++ b/src/map/if/ifCut.c @@ -33,7 +33,7 @@ ABC_NAMESPACE_IMPL_START /**Function************************************************************* - Synopsis [Returns 1 if pDom is contained in pCut.] + Synopsis [Check correctness of cuts.] Description [] @@ -42,24 +42,71 @@ ABC_NAMESPACE_IMPL_START SeeAlso [] ***********************************************************************/ -static inline int If_CutCheckDominance( If_Cut_t * pDom, If_Cut_t * pCut ) +static inline int If_CutVerifyCut( If_Cut_t * pBase, If_Cut_t * pCut ) // check if pCut is contained in pBase { + int nSizeB = pBase->nLeaves; + int nSizeC = pCut->nLeaves; + int * pB = pBase->pLeaves; + int * pC = pCut->pLeaves; int i, k; - for ( i = 0; i < (int)pDom->nLeaves; i++ ) + for ( i = 0; i < nSizeC; i++ ) { - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) + for ( k = 0; k < nSizeB; k++ ) + if ( pC[i] == pB[k] ) break; - if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut + if ( k == nSizeB ) return 0; } - // every node in pDom is contained in pCut + return 1; +} +int If_CutVerifyCuts( If_Set_t * pCutSet, int fOrdered ) +{ + static int Count = 0; + If_Cut_t * pCut0, * pCut1; + int i, k, m, n, Value; + assert( pCutSet->nCuts > 0 ); + for ( i = 0; i < pCutSet->nCuts; i++ ) + { + pCut0 = pCutSet->ppCuts[i]; + if ( fOrdered ) + { + // check duplicates + for ( m = 1; m < (int)pCut0->nLeaves; m++ ) + assert( pCut0->pLeaves[m-1] < pCut0->pLeaves[m] ); + } + else + { + // check duplicates + for ( m = 0; m < (int)pCut0->nLeaves; m++ ) + for ( n = m+1; n < (int)pCut0->nLeaves; n++ ) + assert( pCut0->pLeaves[m] != pCut0->pLeaves[n] ); + } + // check pairs + for ( k = 0; k < pCutSet->nCuts; k++ ) + { + pCut1 = pCutSet->ppCuts[k]; + if ( pCut0 == pCut1 ) + continue; + Count++; + // check containments + Value = If_CutVerifyCut( pCut0, pCut1 ); +// assert( Value == 0 ); + if ( Value ) + { + assert( pCut0->uSign == If_ObjCutSignCompute(pCut0) ); + assert( pCut1->uSign == If_ObjCutSignCompute(pCut1) ); + If_CutPrint( pCut0 ); + If_CutPrint( pCut1 ); + assert( 0 ); + } + } + } return 1; } /**Function************************************************************* - Synopsis [Returns 1 if pDom is equal to pCut.] + Synopsis [Returns 1 if pDom is contained in pCut.] Description [] @@ -68,14 +115,19 @@ static inline int If_CutCheckDominance( If_Cut_t * pDom, If_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -static inline int If_CutCheckEquality( If_Cut_t * pDom, If_Cut_t * pCut ) +static inline int If_CutCheckDominance( If_Cut_t * pDom, If_Cut_t * pCut ) { - int i; - if ( (int)pDom->nLeaves != (int)pCut->nLeaves ) - return 0; + int i, k; + assert( pDom->nLeaves <= pCut->nLeaves ); for ( i = 0; i < (int)pDom->nLeaves; i++ ) - if ( pDom->pLeaves[i] != pCut->pLeaves[i] ) + { + for ( k = 0; k < (int)pCut->nLeaves; k++ ) + if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) + break; + if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut return 0; + } + // every node in pDom is contained in pCut return 1; } @@ -101,7 +153,7 @@ int If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut ) if ( pTemp->nLeaves > pCut->nLeaves ) { // do not fiter the first cut - if ( i == 0 ) + if ( i == 0 && pCutSet->nCuts > 1 && pCutSet->ppCuts[1]->fUseless ) continue; // skip the non-contained cuts if ( (pTemp->uSign & pCut->uSign) != pCut->uSign ) @@ -136,93 +188,7 @@ int If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut ) /**Function************************************************************* - Synopsis [Merges two cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int If_CutMergeOrderedOld( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) -{ - int i, k, c; - assert( pC0->nLeaves >= pC1->nLeaves ); - // the case of the largest cut sizes - if ( pC0->nLeaves == pC->nLimit && pC1->nLeaves == pC->nLimit ) - { - for ( i = 0; i < (int)pC0->nLeaves; i++ ) - if ( pC0->pLeaves[i] != pC1->pLeaves[i] ) - return 0; - for ( i = 0; i < (int)pC0->nLeaves; i++ ) - pC->pLeaves[i] = pC0->pLeaves[i]; - pC->nLeaves = pC0->nLeaves; - return 1; - } - // the case when one of the cuts is the largest - if ( pC0->nLeaves == pC->nLimit ) - { - for ( i = 0; i < (int)pC1->nLeaves; i++ ) - { - for ( k = (int)pC0->nLeaves - 1; k >= 0; k-- ) - if ( pC0->pLeaves[k] == pC1->pLeaves[i] ) - break; - if ( k == -1 ) // did not find - return 0; - } - for ( i = 0; i < (int)pC0->nLeaves; i++ ) - pC->pLeaves[i] = pC0->pLeaves[i]; - pC->nLeaves = pC0->nLeaves; - return 1; - } - - // compare two cuts with different numbers - i = k = 0; - for ( c = 0; c < (int)pC->nLimit; c++ ) - { - if ( k == (int)pC1->nLeaves ) - { - if ( i == (int)pC0->nLeaves ) - { - pC->nLeaves = c; - return 1; - } - pC->pLeaves[c] = pC0->pLeaves[i++]; - continue; - } - if ( i == (int)pC0->nLeaves ) - { - if ( k == (int)pC1->nLeaves ) - { - pC->nLeaves = c; - return 1; - } - pC->pLeaves[c] = pC1->pLeaves[k++]; - continue; - } - if ( pC0->pLeaves[i] < pC1->pLeaves[k] ) - { - pC->pLeaves[c] = pC0->pLeaves[i++]; - continue; - } - if ( pC0->pLeaves[i] > pC1->pLeaves[k] ) - { - pC->pLeaves[c] = pC1->pLeaves[k++]; - continue; - } - pC->pLeaves[c] = pC0->pLeaves[i++]; - k++; - } - if ( i < (int)pC0->nLeaves || k < (int)pC1->nLeaves ) - return 0; - pC->nLeaves = c; - return 1; -} - -/**Function************************************************************* - - Synopsis [Merges two cuts.] + Synopsis [Prepares the object for FPGA mapping.] Description [] @@ -231,33 +197,35 @@ static inline int If_CutMergeOrderedOld( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_ SeeAlso [] ***********************************************************************/ -static inline int If_CutMergeOrdered( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) +int If_CutMergeOrdered_( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) { int nSizeC0 = pC0->nLeaves; int nSizeC1 = pC1->nLeaves; int nLimit = pC0->nLimit; int i, k, c, s; - // the case when one of the cuts is the largest - if ( nSizeC0 == nLimit ) + // both cuts are the largest + if ( nSizeC0 == nLimit && nSizeC1 == nLimit ) { - // the case of the largest cut sizes - if ( nSizeC1 == nLimit ) + for ( i = 0; i < nSizeC0; i++ ) { - for ( i = 0; i < nSizeC0; i++ ) - { - if ( pC0->pLeaves[i] != pC1->pLeaves[i] ) - return 0; - p->pPerm[0][i] = p->pPerm[1][i] = p->pPerm[2][i] = i; - pC->pLeaves[i] = pC0->pLeaves[i]; - } - pC->nLeaves = nLimit; - return 1; + if ( pC0->pLeaves[i] != pC1->pLeaves[i] ) + return 0; + p->pPerm[0][i] = p->pPerm[1][i] = p->pPerm[2][i] = i; + pC->pLeaves[i] = pC0->pLeaves[i]; } + p->nShared = nLimit; + pC->nLeaves = nLimit; + pC->uSign = pC0->uSign | pC1->uSign; + p->uSharedMask = Abc_InfoMask( nLimit ); + return 1; } // compare two cuts with different numbers i = k = c = s = 0; + p->uSharedMask = 0; + if ( nSizeC0 == 0 ) goto FlushCut1; + if ( nSizeC1 == 0 ) goto FlushCut0; while ( 1 ) { if ( c == nLimit ) return 0; @@ -265,20 +233,21 @@ static inline int If_CutMergeOrdered( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * p { p->pPerm[0][i] = c; pC->pLeaves[c++] = pC0->pLeaves[i++]; - if ( i >= nSizeC0 ) goto FlushCut1; + if ( i == nSizeC0 ) goto FlushCut1; } else if ( pC0->pLeaves[i] > pC1->pLeaves[k] ) { p->pPerm[1][k] = c; pC->pLeaves[c++] = pC1->pLeaves[k++]; - if ( k >= nSizeC1 ) goto FlushCut0; + if ( k == nSizeC1 ) goto FlushCut0; } else { + p->uSharedMask |= (1 << c); p->pPerm[0][i] = p->pPerm[1][k] = p->pPerm[2][s++] = c; pC->pLeaves[c++] = pC0->pLeaves[i++]; k++; - if ( i >= nSizeC0 ) goto FlushCut1; - if ( k >= nSizeC1 ) goto FlushCut0; + if ( i == nSizeC0 ) goto FlushCut1; + if ( k == nSizeC1 ) goto FlushCut0; } } @@ -289,7 +258,10 @@ FlushCut0: p->pPerm[0][i] = c; pC->pLeaves[c++] = pC0->pLeaves[i++]; } + p->nShared = s; pC->nLeaves = c; + pC->uSign = pC0->uSign | pC1->uSign; + assert( c > 0 ); return 1; FlushCut1: @@ -299,91 +271,10 @@ FlushCut1: p->pPerm[1][k] = c; pC->pLeaves[c++] = pC1->pLeaves[k++]; } + p->nShared = s; pC->nLeaves = c; - return 1; -} - -/**Function************************************************************* - - Synopsis [Merges two cuts.] - - Description [Special case when the cut is known to exist.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int If_CutMergeOrdered2( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) -{ - int i, k, c; - assert( pC0->nLeaves >= pC1->nLeaves ); - // copy the first cut - for ( i = 0; i < (int)pC0->nLeaves; i++ ) - pC->pLeaves[i] = pC0->pLeaves[i]; - pC->nLeaves = pC0->nLeaves; - // the case when one of the cuts is the largest - if ( pC0->nLeaves == pC->nLimit ) - return 1; - // add nodes of the second cut - k = 0; - for ( i = 0; i < (int)pC1->nLeaves; i++ ) - { - // find k-th node before which i-th node should be added - for ( ; k < (int)pC->nLeaves; k++ ) - if ( pC->pLeaves[k] >= pC1->pLeaves[i] ) - break; - // check the case when this should be the last node - if ( k == (int)pC->nLeaves ) - { - pC->pLeaves[k++] = pC1->pLeaves[i]; - pC->nLeaves++; - continue; - } - // check the case when equal node is found - if ( pC1->pLeaves[i] == pC->pLeaves[k] ) - continue; - // add the node - for ( c = (int)pC->nLeaves; c > k; c-- ) - pC->pLeaves[c] = pC->pLeaves[c-1]; - pC->pLeaves[k++] = pC1->pLeaves[i]; - pC->nLeaves++; - } -/* - assert( pC->nLeaves <= pC->nLimit ); - for ( i = 1; i < (int)pC->nLeaves; i++ ) - assert( pC->pLeaves[i-1] < pC->pLeaves[i] ); -*/ - return 1; -} - -/**Function************************************************************* - - Synopsis [Prepares the object for FPGA mapping.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int If_CutMerge2( If_Man_t * p, If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut ) -{ - assert( pCut->nLimit > 0 ); - // merge the nodes - if ( pCut0->nLeaves < pCut1->nLeaves ) - { - if ( !If_CutMergeOrdered( p, pCut1, pCut0, pCut ) ) - return 0; - } - else - { - if ( !If_CutMergeOrdered( p, pCut0, pCut1, pCut ) ) - return 0; - } - pCut->uSign = pCut0->uSign | pCut1->uSign; - assert( If_CutCheck( pCut ) ); + pC->uSign = pC0->uSign | pC1->uSign; + assert( c > 0 ); return 1; } @@ -398,7 +289,7 @@ int If_CutMerge2( If_Man_t * p, If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * p SeeAlso [] ***********************************************************************/ -int If_CutMerge( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) +int If_CutMergeOrdered( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) { int nSizeC0 = pC0->nLeaves; int nSizeC1 = pC1->nLeaves; @@ -412,68 +303,33 @@ int If_CutMerge( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) { if ( pC0->pLeaves[i] != pC1->pLeaves[i] ) return 0; - p->pPerm[0][i] = p->pPerm[1][i] = p->pPerm[2][i] = i; pC->pLeaves[i] = pC0->pLeaves[i]; } - p->nShared = nLimit; pC->nLeaves = nLimit; pC->uSign = pC0->uSign | pC1->uSign; - p->uSharedMask = Abc_InfoMask( nLimit ); - return 1; - } - // one cut is empty - if ( nSizeC0 == 0 ) - { - assert( pC0->uSign == 0 ); - for ( i = 0; i < nSizeC1; i++ ) - { - pC->pLeaves[i] = pC1->pLeaves[i]; - p->pPerm[1][i] = i; - } - p->nShared = 0; - pC->nLeaves = nSizeC1; - pC->uSign = pC0->uSign | pC1->uSign; - p->uSharedMask = 0; - return 1; - } - if ( nSizeC1 == 0 ) - { - assert( pC1->uSign == 0 ); - for ( i = 0; i < nSizeC0; i++ ) - { - pC->pLeaves[i] = pC0->pLeaves[i]; - p->pPerm[0][i] = i; - } - p->nShared = 0; - pC->nLeaves = nSizeC0; - pC->uSign = pC0->uSign | pC1->uSign; - p->uSharedMask = 0; return 1; } // compare two cuts with different numbers - i = k = c = s = 0; - p->uSharedMask = 0; + i = k = c = s = 0; p->nShared = 0; + if ( nSizeC0 == 0 ) goto FlushCut1; + if ( nSizeC1 == 0 ) goto FlushCut0; while ( 1 ) { if ( c == nLimit ) return 0; if ( pC0->pLeaves[i] < pC1->pLeaves[k] ) { - p->pPerm[0][i] = c; pC->pLeaves[c++] = pC0->pLeaves[i++]; if ( i == nSizeC0 ) goto FlushCut1; } else if ( pC0->pLeaves[i] > pC1->pLeaves[k] ) { - p->pPerm[1][k] = c; pC->pLeaves[c++] = pC1->pLeaves[k++]; if ( k == nSizeC1 ) goto FlushCut0; } else { - p->uSharedMask |= (1 << c); - p->pPerm[0][i] = p->pPerm[1][k] = p->pPerm[2][s++] = c; - pC->pLeaves[c++] = pC0->pLeaves[i++]; k++; + pC->pLeaves[c++] = pC0->pLeaves[i++]; k++; p->nShared++; if ( i == nSizeC0 ) goto FlushCut1; if ( k == nSizeC1 ) goto FlushCut0; } @@ -482,11 +338,7 @@ int If_CutMerge( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC ) FlushCut0: if ( c + nSizeC0 > nLimit + i ) return 0; while ( i < nSizeC0 ) - { - p->pPerm[0][i] = c; pC->pLeaves[c++] = pC0->pLeaves[i++]; - } - p->nShared = s; pC->nLeaves = c; pC->uSign = pC0->uSign | pC1->uSign; return 1; @@ -494,16 +346,57 @@ FlushCut0: FlushCut1: if ( c + nSizeC1 > nLimit + k ) return 0; while ( k < nSizeC1 ) - { - p->pPerm[1][k] = c; pC->pLeaves[c++] = pC1->pLeaves[k++]; - } - p->nShared = s; pC->nLeaves = c; pC->uSign = pC0->uSign | pC1->uSign; return 1; } +/**Function************************************************************* + + Synopsis [Prepares the object for FPGA mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutMerge( If_Man_t * p, If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut ) +{ + int nLutSize = pCut0->nLimit; + int nSize0 = pCut0->nLeaves; + int nSize1 = pCut1->nLeaves; + int * pC0 = pCut0->pLeaves; + int * pC1 = pCut1->pLeaves; + int * pC = pCut->pLeaves; + int i, k, c; + // compare two cuts with different numbers + c = nSize0; p->nShared = 0; + for ( i = 0; i < nSize1; i++ ) + { + for ( k = 0; k < nSize0; k++ ) + if ( pC1[i] == pC0[k] ) + break; + if ( k < nSize0 ) + { + p->pPerm[1][i] = k; + p->nShared++; + continue; + } + if ( c == nLutSize ) + return 0; + p->pPerm[1][i] = c; + pC[c++] = pC1[i]; + } + for ( i = 0; i < nSize0; i++ ) + pC[i] = pC0[i]; + pCut->nLeaves = c; + pCut->uSign = pCut0->uSign | pCut1->uSign; + return 1; +} + /**Function************************************************************* Synopsis [Prepares the object for FPGA mapping.] @@ -598,30 +491,6 @@ int If_CutCompareArea( If_Man_t * p, If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) return 0; } -/**Function************************************************************* - - Synopsis [Sorts the cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManSortCuts( If_Man_t * p, int Mode ) -{ -/* - // sort the cuts - if ( Mode || p->pPars->fArea ) // area - qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareArea ); - else if ( p->pPars->fFancy ) - qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelayOld ); - else - qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelay ); -*/ -} - /**Function************************************************************* Synopsis [Comparison function for two cuts.] diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c index 15094c80..f2075e9f 100644 --- a/src/map/if/ifMan.c +++ b/src/map/if/ifMan.c @@ -154,21 +154,6 @@ void If_ManStop( If_Man_t * p ) extern void If_ManCacheAnalize( If_Man_t * p ); if ( p->pPars->fVerbose && p->vCutData ) If_ManCacheAnalize( p ); -/* - if ( p->pIfDsdMan ) - { - If_DsdMan_t * pNew; - If_DsdManSave( p->pIfDsdMan, NULL ); - pNew = If_DsdManLoad( If_DsdManFileName(p->pIfDsdMan) ); - If_DsdManFree( pNew, 1 ); - } -*/ - { -// extern void If_CluHashFindMedian( If_Man_t * p ); -// extern void If_CluHashTableCheck( If_Man_t * p ); -// If_CluHashFindMedian( p ); -// If_CluHashTableCheck( p ); - } if ( p->pPars->fVerbose && p->vTtMem ) printf( "Unique truth tables = %d. Memory = %.2f MB\n", Vec_MemEntryNum(p->vTtMem), Vec_MemMemory(p->vTtMem) / (1<<20) ); if ( p->pPars->fVerbose && p->nCutsUselessAll ) @@ -452,10 +437,10 @@ void If_ManSetupCutTriv( If_Man_t * p, If_Cut_t * pCut, int ObjId ) pCut->nLeaves = 1; pCut->pLeaves[0] = p->pPars->fLiftLeaves? (ObjId << 8) : ObjId; pCut->uSign = If_ObjCutSign( pCut->pLeaves[0] ); - pCut->iCutFunc = p->pPars->fTruth ? 2 : -1; - pCut->iCutDsd = (p->pPars->fUseDsd || p->pPars->fUseTtPerm) ? 2 : -1; + pCut->iCutFunc = (p->pPars->fTruth || p->pPars->fUseTtPerm) ? 2 : -1; + pCut->iCutDsd = p->pPars->fUseDsd ? 2 : (p->pPars->fUseTtPerm ? 0: -1); assert( pCut->pLeaves[0] < p->vObjs->nSize ); - if ( p->pPars->fUseDsd || p->pPars->fUseTtPerm ) + if ( p->pPars->fUseDsd ) pCut->pPerm[0] = 0; } diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c index 7ee7db22..fff00c0a 100644 --- a/src/map/if/ifMap.c +++ b/src/map/if/ifMap.c @@ -140,7 +140,7 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep { If_Set_t * pCutSet; If_Cut_t * pCut0, * pCut1, * pCut; - int i, k, v; + int i, k, v, fChange; assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->pCutSet->nCuts > 0 ); assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->pCutSet->nCuts > 0 ); @@ -197,28 +197,36 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep if ( If_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->pPars->nLutSize ) continue; // merge the cuts - if ( !If_CutMerge( p, pCut0, pCut1, pCut ) ) - continue; - assert( If_CutCheck( pCut ) ); + if ( p->pPars->fUseTtPerm ) + { + if ( !If_CutMerge( p, pCut0, pCut1, pCut ) ) + continue; + } + else + { + if ( !If_CutMergeOrdered( p, pCut0, pCut1, pCut ) ) + continue; + } if ( pObj->fSpec && pCut->nLeaves == (unsigned)p->pPars->nLutSize ) continue; p->nCutsMerged++; p->nCutsTotal++; // check if this cut is contained in any of the available cuts -// if ( p->pPars->pFuncCost == NULL && If_CutFilter( p, pCut ) ) // do not filter functionality cuts if ( !p->pPars->fSkipCutFilter && If_CutFilter( pCutSet, pCut ) ) continue; // compute the truth table pCut->fCompl = 0; pCut->iCutFunc = -1; pCut->iCutDsd = -1; - if ( p->pPars->fTruth ) + if ( p->pPars->fTruth && !p->pPars->fUseTtPerm ) { // abctime clk = Abc_Clock(); if ( p->pPars->fUseTtPerm ) - If_CutComputeTruthPerm( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 ); + fChange = If_CutComputeTruthPerm( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 ); else - If_CutComputeTruth( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 ); + fChange = If_CutComputeTruth( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 ); + if ( !p->pPars->fSkipCutFilter && fChange && If_CutFilter( pCutSet, pCut ) ) + continue; // p->timeTruth += Abc_Clock() - clk; if ( p->pPars->fUseDsd ) { @@ -283,50 +291,6 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep p->nCuts5a++; } } -/* - if ( p->pPars->fUseDsd ) - { - if ( p->pPars->pLutStruct ) - { - int Value = If_DsdManCheckDec( p->pIfDsdMan, pCut->iCutDsd ); - if ( Value != (int)pCut->fUseless ) - { - if ( pCut->fUseless && !Value ) - p->nCountNonDec[0]++; - if ( !pCut->fUseless && Value ) - p->nCountNonDec[1]++; - -// if ( pCut->fUseless && !Value ) -// printf( "Old does not work. New works.\n" ); - if ( !pCut->fUseless && Value ) - printf( "Old works. New does not work. DSD = %d.\n", Abc_Lit2Var(pCut->iCutDsd) ); - if ( !pCut->fUseless && Value ) - { - extern word If_Dec6Perform( word t, int fDerive ); - extern word * If_DsdManComputeTruth( If_DsdMan_t * p, int iDsd, unsigned char * pPermLits ); - int s; - -// word z, t = *If_CutTruthW(p, pCut); - word z, t = *If_DsdManComputeTruth( p->pIfDsdMan, pCut->iCutDsd, NULL ); - - Extra_PrintHex( stdout, (unsigned *)If_CutTruthW(p, pCut), pCut->nLeaves ); printf( "\n" ); - - Dau_DsdPrintFromTruth( &t, pCut->nLeaves ); -// Dau_DsdPrintFromTruth( If_CutTruthW(p, pCut), pCut->nLeaves ); -// If_DsdManPrintOne( stdout, p->pIfDsdMan, Abc_Lit2Var(pCut->iCutDsd), pCut->pPerm, 1 ); -// printf( "Old works. New does not work. DSD = %d.\n", Abc_Lit2Var(pCut->iCutDsd) ); - - z = If_Dec6Perform( t, 1 ); - If_DecPrintConfig( z ); - - s = If_DsdManCheckXY( p->pIfDsdMan, pCut->iCutDsd, 4, 0, 0, 1 ); - printf( "Confirm %d\n", s ); - s = 0; - } - } - } - } -*/ } // compute the application-specific cost and depth @@ -362,6 +326,7 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPrep // If_CutTraverse( p, pObj, pCut ); } assert( pCutSet->nCuts > 0 ); +// If_CutVerifyCuts( pCutSet, !p->pPars->fUseTtPerm ); // update the best cut if ( !fPreprocess || pCutSet->ppCuts[0]->Delay <= pObj->Required + p->fEpsilon ) diff --git a/src/map/if/ifReduce.c b/src/map/if/ifReduce.c index 838a1b08..fec999cb 100644 --- a/src/map/if/ifReduce.c +++ b/src/map/if/ifReduce.c @@ -27,7 +27,6 @@ ABC_NAMESPACE_IMPL_START /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// -static void If_ManImproveReduce( If_Man_t * p, int nLimit ); static void If_ManImproveExpand( If_Man_t * p, int nLimit ); static void If_ManImproveNodeExpand( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited ); static void If_ManImproveNodePrepare( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld, Vec_Ptr_t * vVisited ); @@ -62,29 +61,6 @@ void If_ManImproveMapping( If_Man_t * p ) p->RequiredGlo, p->AreaGlo, p->nNets, p->dPower, p->nCutsMerged ); Abc_PrintTime( 1, "T", Abc_Clock() - clk ); } - -/* - clk = Abc_Clock(); - If_ManImproveReduce( p, p->pPars->nLutSize ); - If_ManComputeRequired( p, 0 ); - if ( p->pPars->fVerbose ) - { - Abc_Print( 1, "R: Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ", - p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) ); - Abc_PrintTime( 1, "T", Abc_Clock() - clk ); - } -*/ -/* - clk = Abc_Clock(); - If_ManImproveExpand( p, p->pPars->nLutSize ); - If_ManComputeRequired( p, 0 ); - if ( p->pPars->fVerbose ) - { - Abc_Print( 1, "E: Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ", - p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) ); - Abc_PrintTime( 1, "T", Abc_Clock() - clk ); - } -*/ } /**Function************************************************************* @@ -267,6 +243,7 @@ void If_ManImproveNodeUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront Vec_PtrForEachEntry( If_Obj_t *, vFront, pFanin, i ) pCut->pLeaves[i] = pFanin->Id; If_CutOrder( pCut ); + pCut->uSign = If_ObjCutSignCompute(pCut); // ref the new cut If_CutAreaRef( p, pCut ); } @@ -477,101 +454,6 @@ void If_ManImproveNodeFaninCompact( If_Man_t * p, If_Obj_t * pObj, int nLimit, V } - - - -/**Function************************************************************* - - Synopsis [Performs fast mapping for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveNodeReduce( If_Man_t * p, If_Obj_t * pObj, int nLimit ) -{ -/* - If_Cut_t * pCut, * pCut0, * pCut1, * pCutR; - If_Obj_t * pFanin0, * pFanin1; - float AreaBef, AreaAft; - int RetValue; - - assert( nLimit <= 32 ); - assert( If_ObjIsAnd(pObj) ); - // get the fanins - pFanin0 = If_ObjFanin0(pObj); - pFanin1 = If_ObjFanin1(pObj); - // get the cuts - pCut = If_ObjCutBest(pObj); - pCut0 = If_ObjIsCi(pFanin0) ? If_ObjCutTriv(pFanin0) : If_ObjCutBest(pFanin0); - pCut1 = If_ObjIsCi(pFanin1) ? If_ObjCutTriv(pFanin1) : If_ObjCutBest(pFanin1); - assert( pCut->Delay <= pObj->Required + p->fEpsilon ); - - // deref the cut if the node is refed - if ( pObj->nRefs > 0 ) - If_CutAreaDeref( p, pCut ); - // get the area - AreaBef = If_CutAreaDerefed( p, pCut ); - // get the fanin support - if ( pFanin0->nRefs > 2 && pCut0->Delay < pObj->Required + p->fEpsilon ) -// if ( pSupp0->nRefs > 0 && pSupp0->Delay < pSupp->DelayR ) // this leads to 2% worse results - { - pCut0 = If_ObjCutTriv(pFanin0); - } - // get the fanin support - if ( pFanin1->nRefs > 2 && pCut1->Delay < pObj->Required + p->fEpsilon ) -// if ( pSupp1->nRefs > 0 && pSupp1->Delay < pSupp->DelayR ) - { - pCut1 = If_ObjCutTriv(pFanin1); - } - - // merge the cuts - pCutR = p->ppCuts[0]; - RetValue = If_CutMerge( pCut0, pCut1, pCutR ); - // try very simple cut - if ( !RetValue ) - { - RetValue = If_CutMerge( If_ObjCutTriv(pFanin0), If_ObjCutTriv(pFanin1), pCutR ); - assert( RetValue == 1 ); - } - if ( RetValue ) - { - pCutR->Delay = If_CutDelay( p, pObj, pCutR ); - AreaAft = If_CutAreaDerefed( p, pCutR ); - // update the best cut - if ( AreaAft < AreaBef - p->fEpsilon && pCutR->Delay < pObj->Required + p->fEpsilon ) - If_CutCopy( p, pCut, pCutR ); - } - // recompute the delay of the best cut - pCut->Delay = If_CutDelay( p, pObj, pCut ); - // ref the cut if the node is refed - if ( pObj->nRefs > 0 ) - If_CutRef( p, pCut ); -*/ -} - -/**Function************************************************************* - - Synopsis [Performs area recovery for each node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void If_ManImproveReduce( If_Man_t * p, int nLimit ) -{ - If_Obj_t * pObj; - int i; - If_ManForEachNode( p, pObj, i ) - If_ManImproveNodeReduce( p, pObj, nLimit ); -} - //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/map/if/ifTruth.c b/src/map/if/ifTruth.c index 9a20ac71..7dbb5144 100644 --- a/src/map/if/ifTruth.c +++ b/src/map/if/ifTruth.c @@ -44,7 +44,7 @@ ABC_NAMESPACE_IMPL_START SeeAlso [] ***********************************************************************/ -void If_CutTruthPermute( word * pTruth, int nLeaves, int nVars, int nWords, float * pDelays, int * pVars, char * pPerm ) +void If_CutTruthPermute( word * pTruth, int nLeaves, int nVars, int nWords, float * pDelays, int * pVars ) { while ( 1 ) { @@ -55,8 +55,6 @@ void If_CutTruthPermute( word * pTruth, int nLeaves, int nVars, int nWords, floa continue; ABC_SWAP( float, pDelays[i], pDelays[i+1] ); ABC_SWAP( int, pVars[i], pVars[i+1] ); - if ( pPerm ) - ABC_SWAP( char, pPerm[i], pPerm[i+1] ); if ( pTruth ) Abc_TtSwapAdjacent( pTruth, nWords, i ); fChange = 1; @@ -70,20 +68,16 @@ void If_CutRotatePins( If_Man_t * p, If_Cut_t * pCut ) If_Obj_t * pLeaf; float PinDelays[IF_MAX_LUTSIZE]; int i, truthId; + assert( !p->pPars->fUseTtPerm ); If_CutForEachLeaf( p, pCut, pLeaf, i ) PinDelays[i] = If_ObjCutBest(pLeaf)->Delay; if ( p->vTtMem == NULL ) { - If_CutTruthPermute( NULL, If_CutLeaveNum(pCut), pCut->nLimit, p->nTruth6Words, PinDelays, If_CutLeaves(pCut), NULL ); - return; - } - if ( p->pPars->fUseTtPerm ) - { - If_CutTruthPermute( NULL, If_CutLeaveNum(pCut), pCut->nLimit, p->nTruth6Words, PinDelays, If_CutLeaves(pCut), pCut->pPerm ); + If_CutTruthPermute( NULL, If_CutLeaveNum(pCut), pCut->nLimit, p->nTruth6Words, PinDelays, If_CutLeaves(pCut) ); return; } Abc_TtCopy( p->puTempW, If_CutTruthWR(p, pCut), p->nTruth6Words, 0 ); - If_CutTruthPermute( p->puTempW, If_CutLeaveNum(pCut), pCut->nLimit, p->nTruth6Words, PinDelays, If_CutLeaves(pCut), NULL ); + If_CutTruthPermute( p->puTempW, If_CutLeaveNum(pCut), pCut->nLimit, p->nTruth6Words, PinDelays, If_CutLeaves(pCut) ); truthId = Vec_MemHashInsert( p->vTtMem, p->puTempW ); pCut->iCutFunc = Abc_Var2Lit( truthId, If_CutTruthIsCompl(pCut) ); assert( (p->puTempW[0] & 1) == 0 ); @@ -102,7 +96,7 @@ void If_CutRotatePins( If_Man_t * p, If_Cut_t * pCut ) ***********************************************************************/ int If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 ) { - int fCompl, truthId, nLeavesNew; + int fCompl, truthId, nLeavesNew, RetValue = 0; int iFuncLit0 = pCut0->iCutFunc; int iFuncLit1 = pCut1->iCutFunc; int nWords = Abc_TtWordNum( pCut->nLimit ); @@ -124,6 +118,7 @@ int If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_ { pCut->nLeaves = nLeavesNew; pCut->uSign = If_ObjCutSignCompute( pCut ); + RetValue = 1; } } truthId = Vec_MemHashInsert( p->vTtMem, pTruth ); @@ -137,7 +132,7 @@ int If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_ Abc_TtCanonicize( pCopy, pCut->nLimit, pCanonPerm ); } #endif - return 1; + return RetValue; } /**Function************************************************************* -- cgit v1.2.3