summaryrefslogtreecommitdiffstats
path: root/src/map/if
diff options
context:
space:
mode:
Diffstat (limited to 'src/map/if')
-rw-r--r--src/map/if/if.h44
-rw-r--r--src/map/if/ifCore.c41
-rw-r--r--src/map/if/ifMan.c9
-rw-r--r--src/map/if/ifMap.c223
-rw-r--r--src/map/if/ifReduce.c576
-rw-r--r--src/map/if/ifSelect.c175
-rw-r--r--src/map/if/ifSeq.c170
-rw-r--r--src/map/if/module.make4
8 files changed, 1173 insertions, 69 deletions
diff --git a/src/map/if/if.h b/src/map/if/if.h
index a1d2d41b..31c07528 100644
--- a/src/map/if/if.h
+++ b/src/map/if/if.h
@@ -55,7 +55,7 @@ typedef enum {
IF_BO, // 6: box output
IF_BOX, // 7: box
IF_VOID // 8: unused object
-} Hop_Type_t;
+} If_Type_t;
////////////////////////////////////////////////////////////////////////
/// BASIC TYPES ///
@@ -75,8 +75,10 @@ struct If_Par_t_
If_Lib_t * pLutLib; // the LUT library
int nCutsMax; // the max number of cuts
int fVerbose; // the verbosity flag
+ int fPreprocess; // preprossing
int fArea; // area-oriented mapping
int fFancy; // a fancy feature
+ int fExpRed; // expand/reduce of the best cuts
int fLatchPaths; // reset timing on latch paths
int fSeq; // sequential mapping
int nLatches; // the number of latches
@@ -115,6 +117,7 @@ struct If_Man_t_
int nCutsUsed; // the number of cuts currently used
int nCutsMerged; // the total number of cuts merged
int nCutsMax; // the maximum number of cuts at a node
+ float Fi; // the current value of the clock period (for seq mapping)
// memory management
Mem_Fixed_t * pMem; // memory manager
int nEntrySize; // the size of the entry
@@ -127,15 +130,16 @@ struct If_Man_t_
// priority cut
struct If_Cut_t_
{
- float Delay; // the delay of the cut
- float Area; // the area of the cut
- If_Cut_t * pOne; // the parent cut
- If_Cut_t * pTwo; // the parent cut
- char fCompl0; // the complemented attribute
- char fCompl1; // the complemented attribute
- char Phase; // the complemented attribute
- char nLeaves; // the number of leaves
- int * pLeaves; // the array of fanins
+ float Delay; // delay of the cut
+ float Area; // area (or area-flow) of the cut
+ If_Cut_t * pOne; // parent cut
+ If_Cut_t * pTwo; // parent cut
+ unsigned uSign; // cut signature
+ char fCompl0; // complemented attribute
+ char fCompl1; // complemented attribute
+ char Phase; // complemented attribute
+ char nLeaves; // number of leaves
+ int * pLeaves; // array of fanins
};
// node extension
@@ -149,8 +153,7 @@ struct If_Obj_t_
unsigned Level : 24; // logic level of the node
int Id; // integer ID
int nRefs; // the number of references
- short nCuts; // the number of cuts
- short iCut; // the number of the best cut
+ int nCuts; // the number of cuts
If_Obj_t * pFanin0; // the first fanin
If_Obj_t * pFanin1; // the second fanin
If_Obj_t * pEquiv; // the choice node
@@ -188,7 +191,8 @@ static inline void If_ObjSetChoice( If_Obj_t * pObj, If_Obj_t * pEqu ) { p
static inline If_Cut_t * If_ObjCut( If_Obj_t * pObj, int iCut ) { return pObj->Cuts + iCut; }
static inline If_Cut_t * If_ObjCutTriv( If_Obj_t * pObj ) { return pObj->Cuts; }
-static inline If_Cut_t * If_ObjCutBest( If_Obj_t * pObj ) { return pObj->Cuts + pObj->iCut; }
+static inline If_Cut_t * If_ObjCutBest( If_Obj_t * pObj ) { return pObj->Cuts + 1; }
+static inline unsigned If_ObjCutSign( unsigned ObjId ) { return (1 << (ObjId % 31)); }
static inline void * If_CutData( If_Cut_t * pCut ) { return *(void **)pCut; }
static inline void If_CutSetData( If_Cut_t * pCut, void * pData ) { *(void **)pCut = pData; }
@@ -239,6 +243,7 @@ static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { r
/*=== ifCore.c ==========================================================*/
extern int If_ManPerformMapping( If_Man_t * p );
+extern int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fRequired );
/*=== ifMan.c ==========================================================*/
extern If_Man_t * If_ManStart( If_Par_t * pPars );
extern void If_ManStop( If_Man_t * p );
@@ -247,6 +252,19 @@ extern If_Obj_t * If_ManCreatePo( If_Man_t * p, If_Obj_t * pDriver, int fCo
extern If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, int fCompl0, If_Obj_t * pFan1, int fCompl1 );
/*=== ifMap.c ==========================================================*/
extern void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode );
+extern float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut, int nLevels );
+extern float If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut, int nLevels );
+extern float If_CutDeref( If_Man_t * p, If_Cut_t * pCut, int nLevels );
+extern float If_CutRef( If_Man_t * p, If_Cut_t * pCut, int nLevels );
+extern void If_CutPrint( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutDelay( If_Man_t * p, If_Cut_t * pCut );
+extern float If_CutFlow( If_Man_t * p, If_Cut_t * pCut );
+extern int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut, int nLimit );
+extern void If_CutCopy( If_Cut_t * pCutDest, If_Cut_t * pCutSrc );
+/*=== ifReduce.c ==========================================================*/
+extern void If_ManImproveMapping( If_Man_t * p );
+/*=== ifSelect.c ==========================================================*/
+extern void If_ManPerformMappingPreprocess( If_Man_t * p );
/*=== ifUtil.c ==========================================================*/
extern float If_ManDelayMax( If_Man_t * p );
extern void If_ManCleanNodeCopy( If_Man_t * p );
diff --git a/src/map/if/ifCore.c b/src/map/if/ifCore.c
index 37a22d8b..e139e14b 100644
--- a/src/map/if/ifCore.c
+++ b/src/map/if/ifCore.c
@@ -24,8 +24,6 @@
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
-static int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode );
-
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
@@ -44,7 +42,7 @@ static int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode );
int If_ManPerformMapping( If_Man_t * p )
{
If_Obj_t * pObj;
- int nItersFlow = 2;
+ int nItersFlow = 1;
int nItersArea = 1;
int clkTotal = clock();
int i;
@@ -56,13 +54,27 @@ int If_ManPerformMapping( If_Man_t * p )
If_ManForEachPi( p, pObj, i )
pObj->EstRefs = (float)1.0;
// delay oriented mapping
- If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0 );
+ if ( p->pPars->fPreprocess && !p->pPars->fArea && p->pPars->nCutsMax >= 4 )
+ If_ManPerformMappingPreprocess( p );
+ else
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1 );
+ // try to improve area by expanding and reducing the cuts
+ if ( p->pPars->fExpRed )
+ If_ManImproveMapping( p );
// area flow oriented mapping
for ( i = 0; i < nItersFlow; i++ )
- If_ManPerformMappingRound( p, p->pPars->nCutsMax, 1 );
+ {
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 1, 1 );
+ if ( p->pPars->fExpRed )
+ If_ManImproveMapping( p );
+ }
// area oriented mapping
for ( i = 0; i < nItersArea; i++ )
- If_ManPerformMappingRound( p, p->pPars->nCutsMax, 2 );
+ {
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 2, 1 );
+ if ( p->pPars->fExpRed )
+ If_ManImproveMapping( p );
+ }
if ( p->pPars->fVerbose )
{
PRT( "Total time", clock() - clkTotal );
@@ -81,7 +93,7 @@ int If_ManPerformMapping( If_Man_t * p )
SeeAlso []
***********************************************************************/
-int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode )
+int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fRequired )
{
If_Obj_t * pObj;
int i, clk = clock();
@@ -94,15 +106,18 @@ int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode )
If_ManForEachNode( p, pObj, i )
If_ObjPerformMapping( p, pObj, Mode );
// compute required times and stats
- If_ManComputeRequired( p, Mode==0 );
- if ( p->pPars->fVerbose )
+ if ( fRequired )
{
- char Symb = (Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A');
- printf( "%c: Del = %6.2f. Area = %8.2f. Cuts = %6d. Lim = %2d. Ave = %5.2f. ",
- Symb, p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
- PRT( "T", clock() - clk );
+ If_ManComputeRequired( p, Mode==0 );
+ if ( p->pPars->fVerbose )
+ {
+ char Symb = (Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A');
+ printf( "%c: Del = %6.2f. Area = %8.2f. Cuts = %6d. Lim = %2d. Ave = %5.2f. ",
+ Symb, p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ PRT( "T", clock() - clk );
// printf( "Max number of cuts = %d. Average number of cuts = %5.2f.\n",
// p->nCutsMax, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ }
}
return 1;
}
diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c
index bc13c6f0..b0c12fea 100644
--- a/src/map/if/ifMan.c
+++ b/src/map/if/ifMan.c
@@ -191,6 +191,7 @@ If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, int fCompl0, If_Obj_
***********************************************************************/
If_Obj_t * If_ManSetupObj( If_Man_t * p )
{
+ If_Cut_t * pCut;
If_Obj_t * pObj;
int i, * pArrays;
// get memory for the object
@@ -204,10 +205,12 @@ If_Obj_t * If_ManSetupObj( If_Man_t * p )
pObj->Id = Vec_PtrSize(p->vObjs);
Vec_PtrPush( p->vObjs, pObj );
// assign elementary cut
+ pCut = pObj->Cuts;
+ pCut->nLeaves = 1;
+ pCut->pLeaves[0] = p->pPars->fSeq? (pObj->Id << 8) : pObj->Id;
+ pCut->uSign = If_ObjCutSign( pCut->pLeaves[0] );
+ // set the number of cuts
pObj->nCuts = 1;
- pObj->Cuts[0].nLeaves = 1;
- pObj->Cuts[0].pLeaves[0] = pObj->Id;
- pObj->iCut = 0;
// set the required times
pObj->Required = IF_FLOAT_LARGE;
return pObj;
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;
diff --git a/src/map/if/ifReduce.c b/src/map/if/ifReduce.c
new file mode 100644
index 00000000..5c8da0d0
--- /dev/null
+++ b/src/map/if/ifReduce.c
@@ -0,0 +1,576 @@
+/**CFile****************************************************************
+
+ FileName [ifExpand.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Incremental improvement of current mapping.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifExpand.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// 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 );
+static void If_ManImproveNodeUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront );
+static void If_ManImproveNodeFaninCompact( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited );
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Improves current mapping using expand/Expand of one cut.]
+
+ Description [Assumes current mapping assigned and required times computed.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveMapping( If_Man_t * p )
+{
+ int clk;
+
+ clk = clock();
+ If_ManImproveExpand( p, p->pPars->nLutSize );
+ If_ManComputeRequired( p, 0 );
+ if ( p->pPars->fVerbose )
+ {
+ printf( "E: Del = %6.2f. Area = %8.2f. Cuts = %6d. Lim = %2d. Ave = %5.2f. ",
+ p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ PRT( "T", clock() - clk );
+ }
+/*
+ clk = clock();
+ If_ManImproveReduce( p, p->pPars->nLutSize );
+ If_ManComputeRequired( p, 0 );
+ if ( p->pPars->fVerbose )
+ {
+ printf( "R: Del = %6.2f. Area = %8.2f. Cuts = %6d. Lim = %2d. Ave = %5.2f. ",
+ p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ PRT( "T", clock() - clk );
+ }
+
+ clk = clock();
+ If_ManImproveExpand( p, p->pPars->nLutSize );
+ If_ManComputeRequired( p, 0 );
+ if ( p->pPars->fVerbose )
+ {
+ printf( "E: Del = %6.2f. Area = %8.2f. Cuts = %6d. Lim = %2d. Ave = %5.2f. ",
+ p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ PRT( "T", clock() - clk );
+ }
+*/
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs area recovery for each node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveExpand( If_Man_t * p, int nLimit )
+{
+ Vec_Ptr_t * vFront, * vFrontOld, * vVisited;
+ If_Obj_t * pObj;
+ int i;
+ vFront = Vec_PtrAlloc( nLimit );
+ vFrontOld = Vec_PtrAlloc( nLimit );
+ vVisited = Vec_PtrAlloc( 100 );
+ // iterate through all nodes in the topological order
+ If_ManForEachNode( p, pObj, i )
+ If_ManImproveNodeExpand( p, pObj, nLimit, vFront, vFrontOld, vVisited );
+ Vec_PtrFree( vFront );
+ Vec_PtrFree( vFrontOld );
+ Vec_PtrFree( vVisited );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Counts the number of nodes with no external fanout.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveCutCost( If_Man_t * p, Vec_Ptr_t * vFront )
+{
+ If_Obj_t * pFanin;
+ int i, Counter = 0;
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ if ( pFanin->nRefs == 0 )
+ Counter++;
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs area recovery for each node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+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 )
+{
+ If_Obj_t * pFanin;
+ If_Cut_t * pCut;
+ int CostBef, CostAft, i;
+ float DelayOld, AreaBef, AreaAft;
+ pCut = If_ObjCutBest(pObj);
+ assert( pCut->Delay <= pObj->Required + p->fEpsilon );
+ if ( pObj->nRefs == 0 )
+ return;
+ // get the delay
+ DelayOld = pCut->Delay;
+ // get the area
+ AreaBef = If_CutAreaRefed( p, pCut, 100000 );
+// if ( AreaBef == 1 )
+// return;
+ // the cut is non-trivial
+ If_ManImproveNodePrepare( p, pObj, nLimit, vFront, vFrontOld, vVisited );
+ // iteratively modify the cut
+ If_CutDeref( p, pCut, 100000 );
+ CostBef = If_ManImproveCutCost( p, vFront );
+ If_ManImproveNodeFaninCompact( p, pObj, nLimit, vFront, vVisited );
+ CostAft = If_ManImproveCutCost( p, vFront );
+ If_CutRef( p, pCut, 100000 );
+ assert( CostBef >= CostAft );
+ // clean up
+ Vec_PtrForEachEntry( vVisited, pFanin, i )
+ pFanin->fMark = 0;
+ // update the node
+ If_ManImproveNodeUpdate( p, pObj, vFront );
+ pCut->Delay = If_CutDelay( p, pCut );
+ // get the new area
+ AreaAft = If_CutAreaRefed( p, pCut, 100000 );
+ if ( AreaAft > AreaBef || pCut->Delay > pObj->Required + p->fEpsilon )
+ {
+ If_ManImproveNodeUpdate( p, pObj, vFrontOld );
+ AreaAft = If_CutAreaRefed( p, pCut, 100000 );
+ assert( AreaAft == AreaBef );
+ pCut->Delay = DelayOld;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs area recovery for each node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveMark_rec( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vVisited )
+{
+ if ( pObj->fMark )
+ return;
+ assert( If_ObjIsAnd(pObj) );
+ If_ManImproveMark_rec( p, If_ObjFanin0(pObj), vVisited );
+ If_ManImproveMark_rec( p, If_ObjFanin1(pObj), vVisited );
+ Vec_PtrPush( vVisited, pObj );
+ pObj->fMark = 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares node mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+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 )
+{
+ If_Cut_t * pCut;
+ If_Obj_t * pLeaf;
+ int i;
+ Vec_PtrClear( vFront );
+ Vec_PtrClear( vFrontOld );
+ Vec_PtrClear( vVisited );
+ // expand the cut downwards from the given place
+ pCut = If_ObjCutBest(pObj);
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ Vec_PtrPush( vFront, pLeaf );
+ Vec_PtrPush( vFrontOld, pLeaf );
+ Vec_PtrPush( vVisited, pLeaf );
+ pLeaf->fMark = 1;
+ }
+ // mark the nodes in the cone
+ If_ManImproveMark_rec( p, pObj, vVisited );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Updates the frontier.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveNodeUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront )
+{
+ If_Cut_t * pCut;
+ If_Obj_t * pFanin;
+ int i;
+ pCut = If_ObjCutBest(pObj);
+ // deref node's cut
+ If_CutDeref( p, pCut, 10000 );
+ // update the node's cut
+ pCut->nLeaves = Vec_PtrSize(vFront);
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ pCut->pLeaves[i] = pFanin->Id;
+ // ref the new cut
+ If_CutRef( p, pCut, 10000 );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if the number of fanins will grow.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeWillGrow( If_Man_t * p, If_Obj_t * pObj )
+{
+ If_Obj_t * pFanin0, * pFanin1;
+ assert( If_ObjIsAnd(pObj) );
+ pFanin0 = If_ObjFanin0(pObj);
+ pFanin1 = If_ObjFanin1(pObj);
+ return !pFanin0->fMark && !pFanin1->fMark;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns the increase in the number of fanins with no external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCost( If_Man_t * p, If_Obj_t * pObj )
+{
+ int Counter = 0;
+ assert( If_ObjIsAnd(pObj) );
+ // check if the node has external refs
+ if ( pObj->nRefs == 0 )
+ Counter--;
+ // increment the number of fanins without external refs
+ if ( !If_ObjFanin0(pObj)->fMark && If_ObjFanin0(pObj)->nRefs == 0 )
+ Counter++;
+ // increment the number of fanins without external refs
+ if ( !If_ObjFanin1(pObj)->fMark && If_ObjFanin1(pObj)->nRefs == 0 )
+ Counter++;
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Updates the frontier.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveNodeFaninUpdate( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ If_Obj_t * pFanin;
+ assert( If_ObjIsAnd(pObj) );
+ Vec_PtrRemove( vFront, pObj );
+ pFanin = If_ObjFanin0(pObj);
+ if ( !pFanin->fMark )
+ {
+ Vec_PtrPush( vFront, pFanin );
+ Vec_PtrPush( vVisited, pFanin );
+ pFanin->fMark = 1;
+ }
+ pFanin = If_ObjFanin1(pObj);
+ if ( !pFanin->fMark )
+ {
+ Vec_PtrPush( vFront, pFanin );
+ Vec_PtrPush( vVisited, pFanin );
+ pFanin->fMark = 1;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCompact0( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ If_Obj_t * pFanin;
+ int i;
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ {
+ if ( If_ObjIsPi(pFanin) )
+ continue;
+ if ( If_ManImproveNodeWillGrow(p, pFanin) )
+ continue;
+ if ( If_ManImproveNodeFaninCost(p, pFanin) <= 0 )
+ {
+ If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited );
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCompact1( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ If_Obj_t * pFanin;
+ int i;
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ {
+ if ( If_ObjIsPi(pFanin) )
+ continue;
+ if ( If_ManImproveNodeFaninCost(p, pFanin) < 0 )
+ {
+ If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited );
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCompact2( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ If_Obj_t * pFanin;
+ int i;
+ Vec_PtrForEachEntry( vFront, pFanin, i )
+ {
+ if ( If_ObjIsPi(pFanin) )
+ continue;
+ if ( If_ManImproveNodeFaninCost(p, pFanin) <= 0 )
+ {
+ If_ManImproveNodeFaninUpdate( p, pFanin, vFront, vVisited );
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManImproveNodeFaninCompact_int( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ if ( If_ManImproveNodeFaninCompact0(p, pObj, nLimit, vFront, vVisited) )
+ return 1;
+ if ( Vec_PtrSize(vFront) < nLimit && If_ManImproveNodeFaninCompact1(p, pObj, nLimit, vFront, vVisited) )
+ return 1;
+ if ( Vec_PtrSize(vFront) < nLimit && If_ManImproveNodeFaninCompact2(p, pObj, nLimit, vFront, vVisited) )
+ return 1;
+ assert( Vec_PtrSize(vFront) <= nLimit );
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Compacts the number of external refs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManImproveNodeFaninCompact( If_Man_t * p, If_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vVisited )
+{
+ while ( If_ManImproveNodeFaninCompact_int( p, pObj, nLimit, vFront, vVisited ) );
+}
+
+
+
+
+
+/**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_ObjIsPi(pFanin0) ? If_ObjCutTriv(pFanin0) : If_ObjCutBest(pFanin0);
+ pCut1 = If_ObjIsPi(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_CutDeref( p, pCut, 100000 );
+ // get the area
+ AreaBef = If_CutAreaDerefed( p, pCut, 100000 );
+ // 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, nLimit );
+ // try very simple cut
+ if ( !RetValue )
+ {
+ RetValue = If_CutMerge( If_ObjCutTriv(pFanin0), If_ObjCutTriv(pFanin1), pCutR, nLimit );
+ assert( RetValue == 1 );
+ }
+ if ( RetValue )
+ {
+ pCutR->Delay = If_CutDelay( p, pCutR );
+ AreaAft = If_CutAreaDerefed( p, pCutR, 100000 );
+ // update the best cut
+ if ( AreaAft < AreaBef - p->fEpsilon && pCutR->Delay < pObj->Required + p->fEpsilon )
+ If_CutCopy( pCut, pCutR );
+ }
+ // recompute the delay of the best cut
+ pCut->Delay = If_CutDelay( p, pCut );
+ // ref the cut if the node is refed
+ if ( pObj->nRefs > 0 )
+ If_CutRef( p, pCut, 100000 );
+}
+
+/**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 ( 278 == i )
+ {
+ int s = 0;
+ }
+ If_ManImproveNodeReduce( p, pObj, nLimit );
+ }
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifSelect.c b/src/map/if/ifSelect.c
new file mode 100644
index 00000000..d54abb29
--- /dev/null
+++ b/src/map/if/ifSelect.c
@@ -0,0 +1,175 @@
+/**CFile****************************************************************
+
+ FileName [ifSelect.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Selects what mapping to use.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifSelect.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+static void If_ManPerformMappingMoveBestCut( If_Man_t * p, int iPosNew, int iPosOld );
+static void If_ManPerformMappingAdjust( If_Man_t * p, int nCuts );
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Merges the results of delay, relaxed delay and area-based mapping.]
+
+ Description [Delay target may be different from minimum delay!!!]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManPerformMappingPreprocess( If_Man_t * p )
+{
+ float delayArea, delayDelay, delayPure;
+ int clk = clock();
+ assert( p->pPars->nCutsMax >= 4 );
+
+ // perform min-area mapping and move the cut to the end
+ p->pPars->fArea = 1;
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 0 );
+ p->pPars->fArea = 0;
+ delayArea = If_ManDelayMax( p );
+ if ( p->pPars->DelayTarget != -1 && delayArea < p->pPars->DelayTarget - p->fEpsilon )
+ delayArea = p->pPars->DelayTarget;
+ If_ManPerformMappingMoveBestCut( p, p->pPars->nCutsMax - 1, 1 );
+
+ // perfrom min-delay mapping and move the cut to the end
+ p->pPars->fFancy = 1;
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax - 1, 0, 0 );
+ p->pPars->fFancy = 0;
+ delayDelay = If_ManDelayMax( p );
+ if ( p->pPars->DelayTarget != -1 && delayDelay < p->pPars->DelayTarget - p->fEpsilon )
+ delayDelay = p->pPars->DelayTarget;
+ If_ManPerformMappingMoveBestCut( p, p->pPars->nCutsMax - 2, 1 );
+
+ // perform min-area mapping
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax - 2, 0, 0 );
+ delayPure = If_ManDelayMax( p );
+ if ( p->pPars->DelayTarget != -1 && delayPure < p->pPars->DelayTarget - p->fEpsilon )
+ delayPure = p->pPars->DelayTarget;
+
+ // decide what to do
+ if ( delayPure < delayDelay - p->fEpsilon && delayPure < delayArea - p->fEpsilon )
+ {
+ // copy the remaining two cuts
+ if ( p->pPars->nCutsMax > 4 )
+ {
+ If_ManPerformMappingMoveBestCut( p, 2, p->pPars->nCutsMax - 2 );
+ If_ManPerformMappingMoveBestCut( p, 3, p->pPars->nCutsMax - 1 );
+ }
+ If_ManComputeRequired( p, 1 );
+ If_ManPerformMappingAdjust( p, 4 );
+ }
+ else if ( delayDelay < delayArea - p->fEpsilon )
+ {
+ If_ManPerformMappingMoveBestCut( p, 1, p->pPars->nCutsMax - 2 );
+ If_ManPerformMappingMoveBestCut( p, 2, p->pPars->nCutsMax - 1 );
+ If_ManComputeRequired( p, 1 );
+ If_ManPerformMappingAdjust( p, 3 );
+ }
+ else
+ {
+ If_ManPerformMappingMoveBestCut( p, 1, p->pPars->nCutsMax - 1 );
+ If_ManComputeRequired( p, 1 );
+ If_ManPerformMappingAdjust( p, 2 );
+ }
+ If_ManComputeRequired( p, 1 );
+ if ( p->pPars->fVerbose )
+ {
+ printf( "S: Del = %6.2f. Area = %8.2f. Cuts = %6d. Lim = %2d. Ave = %5.2f. ",
+ p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ PRT( "T", clock() - clk );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Moves the best cut to the given position.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManPerformMappingMoveBestCut( If_Man_t * p, int iPosNew, int iPosOld )
+{
+ If_Obj_t * pObj;
+ int i;
+ assert( iPosOld != iPosNew );
+ assert( iPosOld > 0 && iPosOld < p->pPars->nCutsMax );
+ assert( iPosNew > 0 && iPosNew < p->pPars->nCutsMax );
+ If_ManForEachNode( p, pObj, i )
+ If_CutCopy( pObj->Cuts + iPosNew, pObj->Cuts + iPosOld );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Adjusts mapping for the given cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManPerformMappingAdjust( If_Man_t * p, int nCuts )
+{
+ If_Cut_t * pCut, * pCutBest;
+ If_Obj_t * pObj;
+ int i, c;
+ assert( nCuts >= 2 && nCuts <= 4 );
+ If_ManForEachNode( p, pObj, i )
+ {
+ pCutBest = NULL;
+ for ( c = 1; c < nCuts; c++ )
+ {
+ pCut = pObj->Cuts + c;
+ pCut->Delay = If_CutDelay( p, pCut );
+ pCut->Area = If_CutFlow( p, pCut );
+ assert( pCutBest || pCut->Delay < pObj->Required + p->fEpsilon );
+ if ( pCutBest == NULL ||
+ (pCut->Delay < pObj->Required + p->fEpsilon &&
+ pCut->Area < pCutBest->Area - p->fEpsilon) )
+ pCutBest = pCut;
+ }
+ assert( pCutBest != NULL );
+ // check if we need to move
+ if ( pCutBest != pObj->Cuts + 1 )
+ If_CutCopy( pObj->Cuts + 1, pCutBest );
+ // set the number of cuts
+ pObj->nCuts = 2;
+ }
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/ifSeq.c b/src/map/if/ifSeq.c
new file mode 100644
index 00000000..ce353f49
--- /dev/null
+++ b/src/map/if/ifSeq.c
@@ -0,0 +1,170 @@
+/**CFile****************************************************************
+
+ FileName [ifSeq.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [FPGA mapping based on priority cuts.]
+
+ Synopsis [Sequential mapping.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - November 21, 2006.]
+
+ Revision [$Id: ifSeq.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "if.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+static void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch );
+static void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj );
+static int If_ManMappingSeqConverged( If_Man_t * p );
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Performs sequential mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManPerformMappingSeq( If_Man_t * p )
+{
+ If_Obj_t * pObj, * pLatch;
+ int i, clkTotal = clock();
+ // set the number of cuts used
+ p->nCutsUsed = p->pPars->nCutsMax;
+ // set arrival times and trivial cuts at const 1 and PIs
+ If_ManConst1(p)->Cuts[0].Delay = 0.0;
+ If_ManForEachPi( p, pObj, i )
+ pObj->Cuts[0].Delay = p->pPars->pTimesArr[i];
+ // set the fanout estimates of the PIs
+ If_ManForEachPi( p, pObj, i )
+ pObj->EstRefs = (float)1.0;
+ // delay oriented mapping
+ p->pPars->fFancy = 1;
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 0 );
+ p->pPars->fFancy = 0;
+
+ // perform iterations over the circuit
+ while ( !If_ManMappingSeqConverged( p ) )
+ {
+ // assign cuts to latches
+ If_ManForEachLatch( p, pLatch, i )
+ If_ObjPerformMappingLI( p, pLatch );
+ // assign cuts to primary inputs
+ If_ManForEachLatch( p, pLatch, i )
+ If_ObjPerformMappingLO( p, pLatch, If_ManPi(p, If_ManPiNum(p) - If_ManPoNum(p) + i) );
+ // map the nodes
+ If_ManForEachNode( p, pObj, i )
+ If_ObjPerformMapping( p, pObj, 0 );
+ }
+
+ if ( p->pPars->fVerbose )
+ {
+ PRT( "Total time", clock() - clkTotal );
+ }
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs sequential mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutLift( If_Cut_t * pCut )
+{
+ int i;
+ for ( i = 0; i < pCut->nLeaves; i++ )
+ pCut->pLeaves[i] = ((pCut->pLeaves[i] >> 8) << 8) | ((pCut->pLeaves[i] & 255) + 1);
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs sequential mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch )
+{
+ If_Obj_t * pFanin;
+ int c;
+ assert( If_ObjIsPo(pLatch) );
+ pFanin = If_ObjFanin0(pLatch);
+ for ( c = 0; c < pFanin->nCuts; c++ )
+ If_CutCopy( pLatch->Cuts + c, pFanin->Cuts + c );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs sequential mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj )
+{
+ If_Cut_t * pCut;
+ int c, Limit = IF_MIN( p->nCuts + 1, p->nCutsUsed );
+ assert( If_ObjIsPo(pLatch) );
+ for ( c = 1; c < Limit; c++ )
+ {
+ pCut = pObj->Cuts + c;
+ If_CutCopy( pCut, pLatch->Cuts + c - 1 );
+ If_CutLift( pCut );
+ pCut->Delay -= p->Fi;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs sequential mapping.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManMappingSeqConverged( If_Man_t * p )
+{
+ return 0;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/map/if/module.make b/src/map/if/module.make
index be044da2..362318da 100644
--- a/src/map/if/module.make
+++ b/src/map/if/module.make
@@ -1,4 +1,8 @@
SRC += src/map/if/ifCore.c \
+ src/map/if/ifCut.c \
src/map/if/ifMan.c \
src/map/if/ifMap.c \
+ src/map/if/ifReduce.c \
+ src/map/if/ifSelect.c \
+ src/map/if/ifSeq.c \
src/map/if/ifUtil.c
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-08 20:37:14 +0000