From 38254947a57b9899909d8fbabfbf784690ed5a68 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 5 Dec 2006 08:01:00 -0800 Subject: Version abc61205 --- src/map/if/ifCut.c | 558 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 557 insertions(+), 1 deletion(-) (limited to 'src/map/if/ifCut.c') diff --git a/src/map/if/ifCut.c b/src/map/if/ifCut.c index 0318e5e5..56e354ce 100644 --- a/src/map/if/ifCut.c +++ b/src/map/if/ifCut.c @@ -28,9 +28,405 @@ /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Returns 1 if pDom is contained in pCut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_CutCheckDominance( If_Cut_t * pDom, If_Cut_t * pCut ) +{ + int i, k; + for ( i = 0; i < (int)pDom->nLeaves; 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; +} + +/**Function************************************************************* + + Synopsis [Returns 1 if pDom is equal to pCut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_CutCheckEquality( If_Cut_t * pDom, If_Cut_t * pCut ) +{ + int i; + if ( (int)pDom->nLeaves != (int)pCut->nLeaves ) + return 0; + for ( i = 0; i < (int)pDom->nLeaves; i++ ) + if ( pDom->pLeaves[i] != pCut->pLeaves[i] ) + return 0; + return 1; +} +/**Function************************************************************* + + Synopsis [Returns 1 if the cut is contained.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutFilter( If_Man_t * p, If_Cut_t * pCut ) +{ + If_Cut_t * pTemp; + int i; + for ( i = 0; i < p->nCuts; i++ ) + { + pTemp = p->ppCuts[i]; + if ( pTemp->nLeaves > pCut->nLeaves ) + { +// continue; + // skip the non-contained cuts + if ( (pTemp->uSign & pCut->uSign) != pCut->uSign ) + continue; + // check containment seriously + if ( If_CutCheckDominance( pCut, pTemp ) ) + { + // removed contained cut + p->ppCuts[i] = p->ppCuts[p->nCuts-1]; + p->ppCuts[p->nCuts-1] = pTemp; + p->nCuts--; + i--; + } + } + else + { + // skip the non-contained cuts + if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign ) + continue; + // check containment seriously + if ( If_CutCheckDominance( pTemp, pCut ) ) + return 1; + } + } + return 0; +} + +/**Function************************************************************* + + Synopsis [Merges two cuts.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_CutMergeOrdered( 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.] + + 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_CutMerge( 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( pCut1, pCut0, pCut ) ) + return 0; + } + else + { + if ( !If_CutMergeOrdered( pCut0, pCut1, pCut ) ) + return 0; + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Prepares the object for FPGA mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutCompareDelay( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) +{ + If_Cut_t * pC0 = *ppC0; + If_Cut_t * pC1 = *ppC1; + if ( pC0->Delay < pC1->Delay - 0.0001 ) + return -1; + if ( pC0->Delay > pC1->Delay + 0.0001 ) + return 1; + if ( pC0->nLeaves < pC1->nLeaves ) + return -1; + if ( pC0->nLeaves > pC1->nLeaves ) + return 1; + if ( pC0->Area < pC1->Area - 0.0001 ) + return -1; + if ( pC0->Area > pC1->Area + 0.0001 ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Prepares the object for FPGA mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutCompareDelayOld( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) +{ + If_Cut_t * pC0 = *ppC0; + If_Cut_t * pC1 = *ppC1; + if ( pC0->Delay < pC1->Delay - 0.0001 ) + return -1; + if ( pC0->Delay > pC1->Delay + 0.0001 ) + return 1; + if ( pC0->Area < pC1->Area - 0.0001 ) + return -1; + if ( pC0->Area > pC1->Area + 0.0001 ) + return 1; + if ( pC0->nLeaves < pC1->nLeaves ) + return -1; + if ( pC0->nLeaves > pC1->nLeaves ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Prepares the object for FPGA mapping.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int If_CutCompareArea( If_Cut_t ** ppC0, If_Cut_t ** ppC1 ) +{ + If_Cut_t * pC0 = *ppC0; + If_Cut_t * pC1 = *ppC1; + if ( pC0->Area < pC1->Area - 0.0001 ) + return -1; + if ( pC0->Area > pC1->Area + 0.0001 ) + return 1; + if ( pC0->nLeaves < pC1->nLeaves ) + return -1; + if ( pC0->nLeaves > pC1->nLeaves ) + return 1; + if ( pC0->Delay < pC1->Delay - 0.0001 ) + return -1; + if ( pC0->Delay > pC1->Delay + 0.0001 ) + return 1; + 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 [Computes delay.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutDelay( If_Man_t * p, If_Cut_t * pCut ) +{ + If_Obj_t * pLeaf; + float Delay; + int i; + assert( pCut->nLeaves > 1 ); + Delay = -IF_FLOAT_LARGE; + If_CutForEachLeaf( p, pCut, pLeaf, i ) + Delay = IF_MAX( Delay, If_ObjCutBest(pLeaf)->Delay ); + return Delay + If_CutLutDelay(p, pCut); +} + /**Function************************************************************* - Synopsis [] + Synopsis [Computes area flow.] Description [] @@ -39,6 +435,166 @@ SeeAlso [] ***********************************************************************/ +float If_CutFlow( If_Man_t * p, If_Cut_t * pCut ) +{ + If_Obj_t * pLeaf; + float Flow; + int i; + assert( pCut->nLeaves > 1 ); + Flow = If_CutLutArea(p, pCut); + If_CutForEachLeaf( p, pCut, pLeaf, i ) + { + if ( pLeaf->nRefs == 0 ) + Flow += If_ObjCutBest(pLeaf)->Area; + else + { + assert( pLeaf->EstRefs > p->fEpsilon ); + Flow += If_ObjCutBest(pLeaf)->Area / pLeaf->EstRefs; + } + } + return Flow; +} + +/**Function************************************************************* + + Synopsis [Computes area of the first level.] + + Description [The cut need to be derefed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels ) +{ + If_Obj_t * pLeaf; + float Area; + int i; + Area = If_CutLutArea(p, pCut); + If_CutForEachLeaf( p, pCut, pLeaf, i ) + { + assert( pLeaf->nRefs > 0 ); + if ( --pLeaf->nRefs > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) + continue; + Area += If_CutDeref( p, If_ObjCutBest(pLeaf), nLevels - 1 ); + } + return Area; +} + +/**Function************************************************************* + + Synopsis [Computes area of the first level.] + + Description [The cut need to be derefed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels ) +{ + If_Obj_t * pLeaf; + float Area; + int i; + Area = If_CutLutArea(p, pCut); + If_CutForEachLeaf( p, pCut, pLeaf, i ) + { + assert( pLeaf->nRefs >= 0 ); + if ( pLeaf->nRefs++ > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) + continue; + Area += If_CutRef( p, If_ObjCutBest(pLeaf), nLevels - 1 ); + } + return Area; +} + +/**Function************************************************************* + + Synopsis [Prints one cut.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void If_CutPrint( If_Man_t * p, If_Cut_t * pCut ) +{ + unsigned i; + printf( "{" ); + for ( i = 0; i < pCut->nLeaves; i++ ) + printf( " %d", pCut->pLeaves[i] ); + printf( " }\n" ); +} + +/**Function************************************************************* + + Synopsis [Computes area of the first level.] + + Description [The cut need to be derefed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut, int nLevels ) +{ + float aResult, aResult2; + assert( pCut->nLeaves > 1 ); + aResult2 = If_CutRef( p, pCut, nLevels ); + aResult = If_CutDeref( p, pCut, nLevels ); + assert( aResult == aResult2 ); + return aResult; +} + +/**Function************************************************************* + + Synopsis [Computes area of the first level.] + + Description [The cut need to be derefed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut, int nLevels ) +{ + float aResult, aResult2; + assert( pCut->nLeaves > 1 ); + aResult2 = If_CutDeref( p, pCut, nLevels ); + aResult = If_CutRef( p, pCut, nLevels ); + assert( aResult == aResult2 ); + return aResult; +} + +/**Function************************************************************* + + Synopsis [Computes area of the first level.] + + Description [The cut need to be derefed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void If_CutCopy( If_Cut_t * pCutDest, If_Cut_t * pCutSrc ) +{ + int * pLeaves; + unsigned * pTruth; + pLeaves = pCutDest->pLeaves; + pTruth = pCutDest->pTruth; + *pCutDest = *pCutSrc; + pCutDest->pLeaves = pLeaves; + pCutDest->pTruth = pTruth; + memcpy( pCutDest->pLeaves, pCutSrc->pLeaves, sizeof(int) * pCutSrc->nLeaves ); + if ( pCutSrc->pTruth ) + memcpy( pCutDest->pTruth, pCutSrc->pTruth, sizeof(unsigned) * If_CutTruthWords(pCutSrc->nLimit) ); +} //////////////////////////////////////////////////////////////////////// /// END OF FILE /// -- cgit v1.2.3