summaryrefslogtreecommitdiffstats
path: root/src/map/if/ifMap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/map/if/ifMap.c')
-rw-r--r--src/map/if/ifMap.c223
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;
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-20 08:25:57 +0000