diff options
Diffstat (limited to 'src/map/if/ifMap.c')
-rw-r--r-- | src/map/if/ifMap.c | 223 |
1 files changed, 183 insertions, 40 deletions
diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c index 0b505062..9134dc9a 100644 --- a/src/map/if/ifMap.c +++ b/src/map/if/ifMap.c @@ -39,6 +39,26 @@ /**Function************************************************************* + Synopsis [Counts the number of 1s in the signature.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int If_WordCountOnes( unsigned uWord ) +{ + uWord = (uWord & 0x55555555) + ((uWord>>1) & 0x55555555); + uWord = (uWord & 0x33333333) + ((uWord>>2) & 0x33333333); + uWord = (uWord & 0x0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F); + uWord = (uWord & 0x00FF00FF) + ((uWord>>8) & 0x00FF00FF); + return (uWord & 0x0000FFFF) + (uWord>>16); +} + +/**Function************************************************************* + Synopsis [Returns 1 if pDom is contained in pCut.] Description [] @@ -95,7 +115,7 @@ static inline int If_CutCheckEquality( If_Cut_t * pDom, If_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -int If_CutFilter( If_Man_t * p, If_Cut_t * pCut ) +int If_CutFilter( If_Man_t * p, If_Cut_t * pCut, int Mode ) { If_Cut_t * pTemp; int i; @@ -103,21 +123,37 @@ int If_CutFilter( If_Man_t * p, If_Cut_t * pCut ) { pTemp = p->ppCuts[i]; if ( pTemp->nLeaves > pCut->nLeaves ) - continue; - // skip the non-contained cuts -// if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign ) + { // continue; - // check containment seriously - if ( If_CutCheckDominance( pTemp, pCut ) ) -// if ( If_CutCheckEquality( pTemp, pCut ) ) - return 1; + // 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 [Prepares the object for FPGA mapping.] + Synopsis [Merges two cuts.] Description [] @@ -126,7 +162,7 @@ int If_CutFilter( If_Man_t * p, If_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimit ) +static inline int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimit ) { int i, k, c; assert( pC0->nLeaves >= pC1->nLeaves ); @@ -203,6 +239,58 @@ int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimi /**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 nLimit ) +{ + int i, k, c; + assert( pC0->nLeaves >= pC1->nLeaves ); + // copy the first cut + for ( i = 0; i < 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 == nLimit ) + return 1; + // add nodes of the second cut + k = 0; + for ( i = 0; i < pC1->nLeaves; i++ ) + { + // find k-th node before which i-th node should be added + for ( ; k < pC->nLeaves; k++ ) + if ( pC->pLeaves[k] >= pC1->pLeaves[i] ) + break; + // check the case when this should be the last node + if ( k == 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 = pC->nLeaves; c > k; c-- ) + pC->pLeaves[c] = pC->pLeaves[c-1]; + pC->pLeaves[k++] = pC1->pLeaves[i]; + pC->nLeaves++; + } + assert( pC->nLeaves <= nLimit ); + for ( i = 1; i < pC->nLeaves; i++ ) + assert( pC->pLeaves[i-1] < pC->pLeaves[i] ); + return 1; +} + +/**Function************************************************************* + Synopsis [Prepares the object for FPGA mapping.] Description [] @@ -212,7 +300,7 @@ int If_CutMergeOrdered( If_Cut_t * pC0, If_Cut_t * pC1, If_Cut_t * pC, int nLimi SeeAlso [] ***********************************************************************/ -static inline int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut, int nLimit ) +int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut, int nLimit ) { // merge the nodes if ( pCut0->nLeaves < pCut1->nLeaves ) @@ -243,17 +331,17 @@ 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 ) + if ( pC0->Delay < pC1->Delay - 0.0001 ) return -1; - if ( pC0->Delay > pC1->Delay ) + 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 ) + if ( pC0->Area < pC1->Area - 0.0001 ) return -1; - if ( pC0->Area > pC1->Area ) + if ( pC0->Area > pC1->Area + 0.0001 ) return 1; return 0; } @@ -273,13 +361,13 @@ 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 ) + if ( pC0->Delay < pC1->Delay - 0.0001 ) return -1; - if ( pC0->Delay > pC1->Delay ) + if ( pC0->Delay > pC1->Delay + 0.0001 ) return 1; - if ( pC0->Area < pC1->Area ) + if ( pC0->Area < pC1->Area - 0.0001 ) return -1; - if ( pC0->Area > pC1->Area ) + if ( pC0->Area > pC1->Area + 0.0001 ) return 1; if ( pC0->nLeaves < pC1->nLeaves ) return -1; @@ -303,17 +391,17 @@ 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 ) + if ( pC0->Area < pC1->Area - 0.0001 ) return -1; - if ( pC0->Area > pC1->Area ) + 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 ) + if ( pC0->Delay < pC1->Delay - 0.0001 ) return -1; - if ( pC0->Delay > pC1->Delay ) + if ( pC0->Delay > pC1->Delay + 0.0001 ) return 1; return 0; } @@ -405,7 +493,7 @@ float If_CutFlow( If_Man_t * p, If_Cut_t * pCut ) SeeAlso [] ***********************************************************************/ -float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels ) +float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels ) { If_Obj_t * pLeaf; float Area; @@ -413,10 +501,10 @@ float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels ) Area = If_CutLutArea(p, pCut); If_CutForEachLeaf( p, pCut, pLeaf, i ) { - assert( pLeaf->nRefs >= 0 ); - if ( pLeaf->nRefs++ > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) + assert( pLeaf->nRefs > 0 ); + if ( --pLeaf->nRefs > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) continue; - Area += If_CutRef( p, If_ObjCutBest(pLeaf), nLevels - 1 ); + Area += If_CutDeref( p, If_ObjCutBest(pLeaf), nLevels - 1 ); } return Area; } @@ -432,7 +520,7 @@ float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels ) SeeAlso [] ***********************************************************************/ -float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels ) +float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels ) { If_Obj_t * pLeaf; float Area; @@ -440,16 +528,36 @@ float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels ) Area = If_CutLutArea(p, pCut); If_CutForEachLeaf( p, pCut, pLeaf, i ) { - assert( pLeaf->nRefs > 0 ); - if ( --pLeaf->nRefs > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) + assert( pLeaf->nRefs >= 0 ); + if ( pLeaf->nRefs++ > 0 || !If_ObjIsAnd(pLeaf) || nLevels == 1 ) continue; - Area += If_CutDeref( p, If_ObjCutBest(pLeaf), nLevels - 1 ); + 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 ) +{ + int 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.] @@ -459,7 +567,7 @@ float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels ) SeeAlso [] ***********************************************************************/ -float If_CutArea( If_Man_t * p, If_Cut_t * pCut, int nLevels ) +float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut, int nLevels ) { float aResult, aResult2; assert( pCut->nLeaves > 1 ); @@ -480,6 +588,27 @@ float If_CutArea( If_Man_t * p, If_Cut_t * pCut, int nLevels ) 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 * pArray; @@ -503,7 +632,7 @@ void If_CutCopy( If_Cut_t * pCutDest, If_Cut_t * pCutSrc ) void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode ) { If_Cut_t * pCut0, * pCut1, * pCut; - int i, k; + int i, k, iCut; // prepare if ( Mode == 0 ) @@ -521,17 +650,22 @@ void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode ) pCut = If_ObjCutBest(pObj); pCut->Delay = If_CutDelay( p, pCut ); assert( pCut->Delay <= pObj->Required + p->fEpsilon ); - pCut->Area = (Mode == 2)? If_CutArea( p, pCut, 100 ) : If_CutFlow( p, pCut ); + pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, 100 ) : If_CutFlow( p, pCut ); // save the best cut from the previous iteration If_CutCopy( p->ppCuts[p->nCuts++], pCut ); p->nCutsMerged++; } + // prepare room for the next cut + iCut = p->nCuts; + pCut = p->ppCuts[iCut]; // generate cuts - pCut = p->ppCuts[p->nCuts]; If_ObjForEachCut( pObj->pFanin0, pCut0, i ) If_ObjForEachCut( pObj->pFanin1, pCut1, k ) { + // make sure K-feasible cut exists + if ( If_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->pPars->nLutSize ) + continue; // prefilter using arrival times if ( Mode && (pCut0->Delay > pObj->Required + p->fEpsilon || pCut1->Delay > pObj->Required + p->fEpsilon) ) continue; @@ -539,7 +673,8 @@ void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode ) if ( !If_CutMerge( pCut0, pCut1, pCut, p->pPars->nLutSize ) ) continue; // check if this cut is contained in any of the available cuts - if ( If_CutFilter( p, pCut ) ) + pCut->uSign = pCut0->uSign | pCut1->uSign; + if ( If_CutFilter( p, pCut, Mode ) ) continue; // check if the cut satisfies the required times pCut->Delay = If_CutDelay( p, pCut ); @@ -549,18 +684,26 @@ void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode ) pCut->pOne = pCut0; pCut->fCompl0 = pObj->fCompl0; pCut->pTwo = pCut1; pCut->fCompl1 = pObj->fCompl1; // pCut->Phase = ... - pCut->Area = (Mode == 2)? If_CutArea( p, pCut, 100 ) : If_CutFlow( p, pCut ); +// pCut->Phase = (char)(int)If_CutAreaDerefed( p, pCut, 1 ); + pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, 100 ) : If_CutFlow( p, pCut ); p->nCutsMerged++; + // make sure the cut is the last one (after filtering it may not be so) + assert( pCut == p->ppCuts[iCut] ); + p->ppCuts[iCut] = p->ppCuts[p->nCuts]; + p->ppCuts[p->nCuts] = pCut; // prepare room for the next cut - pCut = p->ppCuts[++p->nCuts]; + iCut = ++p->nCuts; + pCut = p->ppCuts[iCut]; } +//printf( "%d ", p->nCuts ); assert( p->nCuts > 0 ); + // sort if we have more cuts If_ManSortCuts( p, Mode ); - // take the first + // decide how many cuts to use pObj->nCuts = IF_MIN( p->nCuts + 1, p->nCutsUsed ); + // take the first If_ObjForEachCutStart( pObj, pCut, i, 1 ) If_CutCopy( pCut, p->ppCuts[i-1] ); - pObj->iCut = 1; assert( If_ObjCutBest(pObj)->nLeaves > 1 ); // assign delay of the trivial cut If_ObjCutTriv(pObj)->Delay = If_ObjCutBest(pObj)->Delay; |