summaryrefslogtreecommitdiffstats
path: root/src/map
diff options
context:
space:
mode:
Diffstat (limited to 'src/map')
-rw-r--r--src/map/if/if.h101
-rw-r--r--src/map/if/ifCore.c18
-rw-r--r--src/map/if/ifCut.c33
-rw-r--r--src/map/if/ifMan.c28
-rw-r--r--src/map/if/ifMap.c58
-rw-r--r--src/map/if/ifPrepro.c6
-rw-r--r--src/map/if/ifReduce.c10
-rw-r--r--src/map/if/ifSeq.c357
-rw-r--r--src/map/if/ifTime.c (renamed from src/map/if/ifLib.c)30
-rw-r--r--src/map/if/ifUtil.c220
-rw-r--r--src/map/if/module.make2
11 files changed, 632 insertions, 231 deletions
diff --git a/src/map/if/if.h b/src/map/if/if.h
index f867e85e..1bbed29d 100644
--- a/src/map/if/if.h
+++ b/src/map/if/if.h
@@ -50,8 +50,8 @@ extern "C" {
typedef enum {
IF_NONE, // 0: non-existent object
IF_CONST1, // 1: constant 1
- IF_PI, // 2: primary input
- IF_PO, // 3: primary output
+ IF_CI, // 2: combinational input
+ IF_CO, // 3: combinational output
IF_AND, // 4: AND node
IF_BI, // 5: box input
IF_BO, // 6: box output
@@ -63,9 +63,9 @@ typedef enum {
/// BASIC TYPES ///
////////////////////////////////////////////////////////////////////////
+typedef struct If_Man_t_ If_Man_t;
typedef struct If_Par_t_ If_Par_t;
typedef struct If_Lib_t_ If_Lib_t;
-typedef struct If_Man_t_ If_Man_t;
typedef struct If_Obj_t_ If_Obj_t;
typedef struct If_Cut_t_ If_Cut_t;
@@ -81,7 +81,7 @@ struct If_Par_t_
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 fSeqMap; // sequential mapping
int fVerbose; // the verbosity flag
// internal parameters
int fTruth; // truth table computation enabled
@@ -89,6 +89,7 @@ struct If_Par_t_
int fUseBdds; // sets local BDDs at the nodes
int fUseSops; // sets local SOPs at the nodes
int nLatches; // the number of latches in seq mapping
+ int fLiftLeaves; // shift the leaves for seq mapping
If_Lib_t * pLutLib; // the LUT library
float * pTimesArr; // arrival times
float * pTimesReq; // required times
@@ -113,8 +114,8 @@ struct If_Man_t_
If_Par_t * pPars;
// mapping nodes
If_Obj_t * pConst1; // the constant 1 node
- Vec_Ptr_t * vPis; // the primary inputs
- Vec_Ptr_t * vPos; // the primary outputs
+ Vec_Ptr_t * vCis; // the primary inputs
+ Vec_Ptr_t * vCos; // the primary outputs
Vec_Ptr_t * vObjs; // all objects
Vec_Ptr_t * vMapped; // objects used in the mapping
Vec_Ptr_t * vTemp; // temporary array
@@ -126,10 +127,13 @@ struct If_Man_t_
float AreaGlo; // global area
int nCutsUsed; // the number of cuts currently used
int nCutsMerged; // the total number of cuts merged
- int nCutsSaved; // the total number of cuts saved
- int nCutsMax; // the maximum number of cuts at a node
- float Fi; // the current value of the clock period (for seq mapping)
unsigned * puTemp[4]; // used for the truth table computation
+ // sequential mapping
+ Vec_Ptr_t * vLatchOrder; // topological ordering of latches
+ Vec_Int_t * vLags; // sequentail lags of all nodes
+ int nAttempts; // the number of attempts in binary search
+ int nMaxIters; // the maximum number of iterations
+ int Period; // 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
@@ -168,7 +172,8 @@ struct If_Obj_t_
unsigned fPhase : 1; // phase of the node
unsigned fRepr : 1; // representative of the equivalence class
unsigned fMark : 1; // multipurpose mark
- unsigned Level : 23; // logic level of the node
+ unsigned fVisit : 1; // multipurpose mark
+ unsigned Level : 22; // logic level of the node
int Id; // integer ID
int nRefs; // the number of references
int nCuts; // the number of cuts
@@ -182,19 +187,21 @@ struct If_Obj_t_
};
static inline If_Obj_t * If_ManConst1( If_Man_t * p ) { return p->pConst1; }
-static inline If_Obj_t * If_ManPi( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vPis, i ); }
-static inline If_Obj_t * If_ManPo( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vPos, i ); }
+static inline If_Obj_t * If_ManCi( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCis, i ); }
+static inline If_Obj_t * If_ManCo( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCos, i ); }
static inline If_Obj_t * If_ManObj( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vObjs, i ); }
static inline If_Cut_t * If_ManCut( If_Man_t * p, int i ) { return p->ppCuts[i]; }
-static inline int If_ManPiNum( If_Man_t * p ) { return p->nObjs[IF_PI]; }
-static inline int If_ManPoNum( If_Man_t * p ) { return p->nObjs[IF_PO]; }
+static inline int If_ManCiNum( If_Man_t * p ) { return p->nObjs[IF_CI]; }
+static inline int If_ManCoNum( If_Man_t * p ) { return p->nObjs[IF_CO]; }
static inline int If_ManAndNum( If_Man_t * p ) { return p->nObjs[IF_AND]; }
static inline int If_ManObjNum( If_Man_t * p ) { return Vec_PtrSize(p->vObjs); }
static inline int If_ObjIsConst1( If_Obj_t * pObj ) { return pObj->Type == IF_CONST1; }
-static inline int If_ObjIsPi( If_Obj_t * pObj ) { return pObj->Type == IF_PI; }
-static inline int If_ObjIsPo( If_Obj_t * pObj ) { return pObj->Type == IF_PO; }
+static inline int If_ObjIsCi( If_Obj_t * pObj ) { return pObj->Type == IF_CI; }
+static inline int If_ObjIsCo( If_Obj_t * pObj ) { return pObj->Type == IF_CO; }
+static inline int If_ObjIsPi( If_Obj_t * pObj ) { return If_ObjIsCi(pObj) && pObj->pFanin0 == NULL; }
+static inline int If_ObjIsLatch( If_Obj_t * pObj ) { return If_ObjIsCi(pObj) && pObj->pFanin0 != NULL; }
static inline int If_ObjIsAnd( If_Obj_t * pObj ) { return pObj->Type == IF_AND; }
static inline int If_ObjIsBi( If_Obj_t * pObj ) { return pObj->Type == IF_BI; }
static inline int If_ObjIsBo( If_Obj_t * pObj ) { return pObj->Type == IF_BO; }
@@ -210,9 +217,12 @@ 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 + 1; }
+static inline If_Cut_t * If_ObjCutBest( If_Obj_t * pObj ) { return pObj->Cuts + (int)(pObj->nCuts > 1); }
static inline unsigned If_ObjCutSign( unsigned ObjId ) { return (1 << (ObjId % 31)); }
+static inline float If_ObjLValue( If_Obj_t * pObj ) { return If_ObjCutTriv(pObj)->Delay; }
+static inline void If_ObjSetLValue( If_Obj_t * pObj, float LValue ) { If_ObjCutTriv(pObj)->Delay = LValue; }
+
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; }
@@ -227,8 +237,8 @@ static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { r
/// MACRO DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
-#define IF_MIN(a,b) (((a) < (b))? (a) : (b))
-#define IF_MAX(a,b) (((a) > (b))? (a) : (b))
+#define IF_MIN(a,b) (((a) < (b))? (a) : (b))
+#define IF_MAX(a,b) (((a) > (b))? (a) : (b))
// the small and large numbers (min/max float are 1.17e-38/3.40e+38)
#define IF_FLOAT_LARGE ((float)1.0e+20)
@@ -236,14 +246,20 @@ static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { r
#define IF_INT_LARGE (10000000)
// iterator over the primary inputs
+#define If_ManForEachCi( p, pObj, i ) \
+ Vec_PtrForEachEntry( p->vCis, pObj, i )
+// iterator over the primary outputs
+#define If_ManForEachCo( p, pObj, i ) \
+ Vec_PtrForEachEntry( p->vCos, pObj, i )
+// iterator over the primary inputs
#define If_ManForEachPi( p, pObj, i ) \
- Vec_PtrForEachEntry( p->vPis, pObj, i )
+ Vec_PtrForEachEntryStop( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches )
// iterator over the primary outputs
#define If_ManForEachPo( p, pObj, i ) \
- Vec_PtrForEachEntry( p->vPos, pObj, i )
+ Vec_PtrForEachEntryStop( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches )
// iterator over the latches
#define If_ManForEachLatch( p, pObj, i ) \
- Vec_PtrForEachEntryStart( p->vPos, pObj, i, If_ManPoNum(p) - p->pPars->nLatches )
+ Vec_PtrForEachEntryStart( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches )
// iterator over all objects, including those currently not used
#define If_ManForEachObj( p, pObj, i ) \
Vec_PtrForEachEntry( p->vObjs, pObj, i )
@@ -256,17 +272,22 @@ static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { r
// iterator over cuts of the node
#define If_ObjForEachCutStart( pObj, pCut, i, Start ) \
for ( i = Start; (i < (int)(pObj)->nCuts) && ((pCut) = (pObj)->Cuts + i); i++ )
-// iterator leaves of the cut
+// iterator over the leaves of the cut
+//#define If_CutForEachLeaf( p, pCut, pLeaf, i ) \
+// for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i])); i++ )
#define If_CutForEachLeaf( p, pCut, pLeaf, i ) \
- for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i])); i++ )
+ for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, p->pPars->fLiftLeaves? (pCut)->pLeaves[i] >> 8 : (pCut)->pLeaves[i])); i++ )
+// iterator over the leaves of the sequential cut
+#define If_CutForEachLeafSeq( p, pCut, pLeaf, Shift, i ) \
+ for ( i = 0; (i < (int)(pCut)->nLeaves) && ((pLeaf) = If_ManObj(p, (pCut)->pLeaves[i] >> 8)) && (((Shift) = ((pCut)->pLeaves[i] & 255)) >= 0); i++ )
////////////////////////////////////////////////////////////////////////
/// FUNCTION DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
-/*=== ifCore.c ==========================================================*/
+/*=== ifCore.c ===========================================================*/
extern int If_ManPerformMapping( If_Man_t * p );
-/*=== ifCut.c ==========================================================*/
+/*=== ifCut.c ============================================================*/
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 );
@@ -277,35 +298,39 @@ extern float If_CutFlow( If_Man_t * p, If_Cut_t * pCut );
extern float If_CutAverageRefs( If_Man_t * p, If_Cut_t * pCut );
extern int If_CutFilter( If_Man_t * p, If_Cut_t * pCut );
extern int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut );
+extern void If_CutLift( If_Cut_t * pCut );
extern void If_CutCopy( If_Cut_t * pCutDest, If_Cut_t * pCutSrc );
extern void If_ManSortCuts( If_Man_t * p, int Mode );
-/*=== ifLib.c ==========================================================*/
-extern float If_CutDelay( If_Man_t * p, If_Cut_t * pCut );
-extern void If_CutPropagateRequired( If_Man_t * p, If_Cut_t * pCut, float Required );
-/*=== ifMan.c ==========================================================*/
+/*=== ifMan.c =============================================================*/
extern If_Man_t * If_ManStart( If_Par_t * pPars );
extern void If_ManStop( If_Man_t * p );
-extern If_Obj_t * If_ManCreatePi( If_Man_t * p );
-extern If_Obj_t * If_ManCreatePo( If_Man_t * p, If_Obj_t * pDriver, int fCompl0 );
+extern If_Obj_t * If_ManCreateCi( If_Man_t * p );
+extern If_Obj_t * If_ManCreateCo( If_Man_t * p, If_Obj_t * pDriver, int fCompl0 );
extern If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, int fCompl0, If_Obj_t * pFan1, int fCompl1 );
extern void If_ManCreateChoice( If_Man_t * p, If_Obj_t * pRepr );
-/*=== ifMap.c ==========================================================*/
-extern void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode );
+/*=== ifMap.c =============================================================*/
+extern void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode );
+extern void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode );
extern int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fRequired, char * pLabel );
/*=== ifPrepro.c ==========================================================*/
extern void If_ManPerformMappingPreprocess( If_Man_t * p );
/*=== ifReduce.c ==========================================================*/
extern void If_ManImproveMapping( If_Man_t * p );
-/*=== ifSeq.c ==========================================================*/
+/*=== ifSeq.c =============================================================*/
extern int If_ManPerformMappingSeq( If_Man_t * p );
-/*=== ifTruth.c ==========================================================*/
+/*=== ifTime.c ============================================================*/
+extern float If_CutDelay( If_Man_t * p, If_Cut_t * pCut );
+extern void If_CutPropagateRequired( If_Man_t * p, If_Cut_t * pCut, float Required );
+/*=== ifTruth.c ===========================================================*/
extern void If_CutComputeTruth( If_Man_t * p, If_Cut_t * pCut, If_Cut_t * pCut0, If_Cut_t * pCut1, int fCompl0, int fCompl1 );
-/*=== ifUtil.c ==========================================================*/
-extern float If_ManDelayMax( If_Man_t * p );
+/*=== ifUtil.c ============================================================*/
extern void If_ManCleanNodeCopy( If_Man_t * p );
extern void If_ManCleanCutData( If_Man_t * p );
+extern void If_ManCleanMarkV( If_Man_t * p );
+extern float If_ManDelayMax( If_Man_t * p, int fSeq );
extern void If_ManComputeRequired( If_Man_t * p, int fFirstTime );
extern float If_ManScanMapping( If_Man_t * p );
+extern float If_ManScanMappingSeq( If_Man_t * p );
#ifdef __cplusplus
}
diff --git a/src/map/if/ifCore.c b/src/map/if/ifCore.c
index c40ed893..38983832 100644
--- a/src/map/if/ifCore.c
+++ b/src/map/if/ifCore.c
@@ -45,13 +45,25 @@ int If_ManPerformMapping( If_Man_t * p )
int nItersFlow = 1;
int nItersArea = 2;
int clkTotal = clock();
- int i;
+ int RetValue, i;
+
+ // try sequential mapping
+ if ( p->pPars->fSeqMap )
+ {
+ RetValue = If_ManPerformMappingSeq( p );
+ if ( p->pPars->fVerbose )
+ {
+ PRT( "Total time", clock() - clkTotal );
+ }
+ return RetValue;
+ }
+
// set arrival times and trivial cuts at const 1 and PIs
If_ManConst1(p)->Cuts[0].Delay = 0.0;
- If_ManForEachPi( p, pObj, i )
+ If_ManForEachCi( p, pObj, i )
pObj->Cuts[0].Delay = p->pPars->pTimesArr[i];
// set the fanout estimates of the PIs
- If_ManForEachPi( p, pObj, i )
+ If_ManForEachCi( p, pObj, i )
pObj->EstRefs = (float)1.0;
// delay oriented mapping
if ( p->pPars->fPreprocess && !p->pPars->fArea && p->pPars->nCutsMax >= 4 )
diff --git a/src/map/if/ifCut.c b/src/map/if/ifCut.c
index 06a020a6..5366aaf5 100644
--- a/src/map/if/ifCut.c
+++ b/src/map/if/ifCut.c
@@ -423,13 +423,15 @@ float If_CutFlow( If_Man_t * p, If_Cut_t * pCut )
If_Obj_t * pLeaf;
float Flow;
int i;
- assert( pCut->nLeaves > 1 );
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
Flow = If_CutLutArea(p, pCut);
If_CutForEachLeaf( p, pCut, pLeaf, i )
{
if ( pLeaf->nRefs == 0 )
Flow += If_ObjCutBest(pLeaf)->Area;
- else
+ else if ( p->pPars->fSeqMap ) // seq
+ Flow += If_ObjCutBest(pLeaf)->Area / pLeaf->nRefs;
+ else
{
assert( pLeaf->EstRefs > p->fEpsilon );
Flow += If_ObjCutBest(pLeaf)->Area / pLeaf->EstRefs;
@@ -453,7 +455,7 @@ float If_CutAverageRefs( If_Man_t * p, If_Cut_t * pCut )
{
If_Obj_t * pLeaf;
int nRefsTotal, i;
- assert( pCut->nLeaves > 1 );
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
nRefsTotal = 0;
If_CutForEachLeaf( p, pCut, pLeaf, i )
nRefsTotal += pLeaf->nRefs;
@@ -569,7 +571,7 @@ void If_CutPrintTiming( If_Man_t * p, If_Cut_t * pCut )
float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut, int nLevels )
{
float aResult, aResult2;
- assert( pCut->nLeaves > 1 );
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
aResult2 = If_CutRef( p, pCut, nLevels );
aResult = If_CutDeref( p, pCut, nLevels );
assert( aResult == aResult2 );
@@ -590,7 +592,7 @@ float If_CutAreaDerefed( If_Man_t * p, If_Cut_t * pCut, int nLevels )
float If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut, int nLevels )
{
float aResult, aResult2;
- assert( pCut->nLeaves > 1 );
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
aResult2 = If_CutDeref( p, pCut, nLevels );
aResult = If_CutRef( p, pCut, nLevels );
assert( aResult == aResult2 );
@@ -599,6 +601,27 @@ float If_CutAreaRefed( If_Man_t * p, If_Cut_t * pCut, int nLevels )
/**Function*************************************************************
+ Synopsis [Moves the cut over the latch.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutLift( If_Cut_t * pCut )
+{
+ unsigned i;
+ for ( i = 0; i < pCut->nLeaves; i++ )
+ {
+ assert( (pCut->pLeaves[i] & 255) < 255 );
+ pCut->pLeaves[i]++;
+ }
+}
+
+/**Function*************************************************************
+
Synopsis [Computes area of the first level.]
Description [The cut need to be derefed.]
diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c
index 040b0e4f..84a0c52f 100644
--- a/src/map/if/ifMan.c
+++ b/src/map/if/ifMan.c
@@ -51,8 +51,8 @@ If_Man_t * If_ManStart( If_Par_t * pPars )
p->pPars = pPars;
p->fEpsilon = (float)0.001;
// allocate arrays for nodes
- p->vPis = Vec_PtrAlloc( 100 );
- p->vPos = Vec_PtrAlloc( 100 );
+ p->vCis = Vec_PtrAlloc( 100 );
+ p->vCos = Vec_PtrAlloc( 100 );
p->vObjs = Vec_PtrAlloc( 100 );
p->vMapped = Vec_PtrAlloc( 100 );
p->vTemp = Vec_PtrAlloc( 100 );
@@ -96,11 +96,13 @@ void If_ManStop( If_Man_t * p )
{
If_Cut_t * pTemp;
int i;
- Vec_PtrFree( p->vPis );
- Vec_PtrFree( p->vPos );
+ Vec_PtrFree( p->vCis );
+ Vec_PtrFree( p->vCos );
Vec_PtrFree( p->vObjs );
Vec_PtrFree( p->vMapped );
Vec_PtrFree( p->vTemp );
+ if ( p->vLatchOrder ) Vec_PtrFree( p->vLatchOrder );
+ if ( p->vLags ) Vec_IntFree( p->vLags );
Mem_FixedStop( p->pMem, 0 );
// free pars memory
if ( p->pPars->pTimesArr )
@@ -129,13 +131,13 @@ void If_ManStop( If_Man_t * p )
SeeAlso []
***********************************************************************/
-If_Obj_t * If_ManCreatePi( If_Man_t * p )
+If_Obj_t * If_ManCreateCi( If_Man_t * p )
{
If_Obj_t * pObj;
pObj = If_ManSetupObj( p );
- pObj->Type = IF_PI;
- Vec_PtrPush( p->vPis, pObj );
- p->nObjs[IF_PI]++;
+ pObj->Type = IF_CI;
+ Vec_PtrPush( p->vCis, pObj );
+ p->nObjs[IF_CI]++;
return pObj;
}
@@ -150,15 +152,15 @@ If_Obj_t * If_ManCreatePi( If_Man_t * p )
SeeAlso []
***********************************************************************/
-If_Obj_t * If_ManCreatePo( If_Man_t * p, If_Obj_t * pDriver, int fCompl0 )
+If_Obj_t * If_ManCreateCo( If_Man_t * p, If_Obj_t * pDriver, int fCompl0 )
{
If_Obj_t * pObj;
pObj = If_ManSetupObj( p );
- pObj->Type = IF_PO;
+ pObj->Type = IF_CO;
pObj->fCompl0 = fCompl0;
- Vec_PtrPush( p->vPos, pObj );
+ Vec_PtrPush( p->vCos, pObj );
pObj->pFanin0 = pDriver; pDriver->nRefs++;
- p->nObjs[IF_PO]++;
+ p->nObjs[IF_CO]++;
return pObj;
}
@@ -251,7 +253,7 @@ If_Obj_t * If_ManSetupObj( If_Man_t * p )
// assign elementary cut
pCut = pObj->Cuts;
pCut->nLeaves = 1;
- pCut->pLeaves[0] = p->pPars->fSeq? (pObj->Id << 8) : pObj->Id;
+ pCut->pLeaves[0] = p->pPars->fLiftLeaves? (pObj->Id << 8) : pObj->Id;
pCut->uSign = If_ObjCutSign( pCut->pLeaves[0] );
// set the number of cuts
pObj->nCuts = 1;
diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c
index 743662b0..4d422359 100644
--- a/src/map/if/ifMap.c
+++ b/src/map/if/ifMap.c
@@ -69,27 +69,31 @@ static inline int If_WordCountOnes( unsigned uWord )
SeeAlso []
***********************************************************************/
-void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode )
+void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode )
{
If_Cut_t * pCut0, * pCut1, * pCut;
int i, k, iCut;
- assert( !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->nCuts > 1 );
- assert( !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->nCuts > 1 );
+ assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->nCuts > 1 );
+ assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->nCuts > 1 );
// prepare
- if ( Mode == 0 )
- pObj->EstRefs = (float)pObj->nRefs;
- else if ( Mode == 1 )
- pObj->EstRefs = (float)((2.0 * pObj->EstRefs + pObj->nRefs) / 3.0);
- else if ( Mode == 2 && pObj->nRefs > 0 )
+ if ( !p->pPars->fSeqMap )
+ {
+ if ( Mode == 0 )
+ pObj->EstRefs = (float)pObj->nRefs;
+ else if ( Mode == 1 )
+ pObj->EstRefs = (float)((2.0 * pObj->EstRefs + pObj->nRefs) / 3.0);
+ }
+ if ( Mode && pObj->nRefs > 0 )
If_CutDeref( p, If_ObjCutBest(pObj), 100 );
- // recompute the parameters of the best cut
+ // save the best cut as one of the candidate cuts
p->nCuts = 0;
p->nCutsMerged++;
if ( Mode )
{
+ // recompute the parameters of the best cut
pCut = If_ObjCutBest(pObj);
pCut->Delay = If_CutDelay( p, pCut );
assert( pCut->Delay <= pObj->Required + p->fEpsilon );
@@ -114,12 +118,12 @@ void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode )
continue;
// check if this cut is contained in any of the available cuts
pCut->uSign = pCut0->uSign | pCut1->uSign;
- pCut->fCompl = 0;
// if ( p->pPars->pFuncCost == NULL && If_CutFilter( p, pCut ) ) // do not filter functionality cuts
if ( If_CutFilter( p, pCut ) )
continue;
// the cuts have been successfully merged
// compute the truth table
+ pCut->fCompl = 0;
if ( p->pPars->fTruth )
If_CutComputeTruth( p, pCut, pCut0, pCut1, pObj->fCompl0, pObj->fCompl1 );
// compute the application-specific cost and depth
@@ -149,16 +153,14 @@ void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode )
If_ManSortCuts( p, Mode );
// decide how many cuts to use
pObj->nCuts = IF_MIN( p->nCuts + 1, p->nCutsUsed );
+//printf( "%d(%d) ", p->nCuts, pObj->nCuts );
// take the first
If_ObjForEachCutStart( pObj, pCut, i, 1 )
If_CutCopy( pCut, p->ppCuts[i-1] );
- assert( If_ObjCutBest(pObj)->nLeaves > 1 );
+ assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 );
// ref the selected cut
- if ( Mode == 2 && pObj->nRefs > 0 )
+ if ( Mode && pObj->nRefs > 0 )
If_CutRef( p, If_ObjCutBest(pObj), 100 );
- // find the largest cut
- if ( p->nCutsMax < pObj->nCuts )
- p->nCutsMax = pObj->nCuts;
}
/**Function*************************************************************
@@ -172,14 +174,14 @@ void If_ObjPerformMapping( If_Man_t * p, If_Obj_t * pObj, int Mode )
SeeAlso []
***********************************************************************/
-void If_ObjMergeChoice( If_Man_t * p, If_Obj_t * pObj, int Mode )
+void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode )
{
If_Obj_t * pTemp;
If_Cut_t * pCutTemp, * pCut;
int i, iCut;
assert( pObj->pEquiv != NULL );
// prepare
- if ( Mode == 2 && pObj->nRefs > 0 )
+ if ( Mode && pObj->nRefs > 0 )
If_CutDeref( p, If_ObjCutBest(pObj), 100 );
// prepare room for the next cut
p->nCuts = 0;
@@ -227,13 +229,10 @@ void If_ObjMergeChoice( If_Man_t * p, If_Obj_t * pObj, int Mode )
// take the first
If_ObjForEachCutStart( pObj, pCut, i, 1 )
If_CutCopy( pCut, p->ppCuts[i-1] );
- assert( If_ObjCutBest(pObj)->nLeaves > 1 );
+ assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 );
// ref the selected cut
- if ( Mode == 2 && pObj->nRefs > 0 )
+ if ( Mode && pObj->nRefs > 0 )
If_CutRef( p, If_ObjCutBest(pObj), 100 );
- // find the largest cut
- if ( p->nCutsMax < pObj->nCuts )
- p->nCutsMax = pObj->nCuts;
}
/**Function*************************************************************
@@ -249,25 +248,23 @@ void If_ObjMergeChoice( If_Man_t * p, If_Obj_t * pObj, int Mode )
***********************************************************************/
int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fRequired, char * pLabel )
{
- ProgressBar * pProgress;
+// ProgressBar * pProgress;
If_Obj_t * pObj;
int i, clk = clock();
assert( Mode >= 0 && Mode <= 2 );
// set the cut number
p->nCutsUsed = nCutsUsed;
p->nCutsMerged = 0;
- p->nCutsSaved = 0;
- p->nCutsMax = 0;
// map the internal nodes
- pProgress = Extra_ProgressBarStart( stdout, If_ManObjNum(p) );
+// pProgress = Extra_ProgressBarStart( stdout, If_ManObjNum(p) );
If_ManForEachNode( p, pObj, i )
{
- Extra_ProgressBarUpdate( pProgress, i, pLabel );
- If_ObjPerformMapping( p, pObj, Mode );
+// Extra_ProgressBarUpdate( pProgress, i, pLabel );
+ If_ObjPerformMappingAnd( p, pObj, Mode );
if ( pObj->fRepr )
- If_ObjMergeChoice( p, pObj, Mode );
+ If_ObjPerformMappingChoice( p, pObj, Mode );
}
- Extra_ProgressBarStop( pProgress );
+// Extra_ProgressBarStop( pProgress );
// compute required times and stats
if ( fRequired )
{
@@ -278,7 +275,6 @@ int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fRequi
printf( "%c: Del = %6.2f. Area = %8.2f. Cuts = %8d. 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( "Saved cuts = %d.\n", p->nCutsSaved );
// printf( "Max number of cuts = %d. Average number of cuts = %5.2f.\n",
// p->nCutsMax, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
}
diff --git a/src/map/if/ifPrepro.c b/src/map/if/ifPrepro.c
index 7aec8f53..f331d917 100644
--- a/src/map/if/ifPrepro.c
+++ b/src/map/if/ifPrepro.c
@@ -52,7 +52,7 @@ void If_ManPerformMappingPreprocess( If_Man_t * p )
p->pPars->fArea = 1;
If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 0, "Start delay" );
p->pPars->fArea = 0;
- delayArea = If_ManDelayMax( p );
+ delayArea = If_ManDelayMax( p, 0 );
if ( p->pPars->DelayTarget != -1 && delayArea < p->pPars->DelayTarget - p->fEpsilon )
delayArea = p->pPars->DelayTarget;
If_ManPerformMappingMoveBestCut( p, p->pPars->nCutsMax - 1, 1 );
@@ -61,14 +61,14 @@ void If_ManPerformMappingPreprocess( If_Man_t * p )
p->pPars->fFancy = 1;
If_ManPerformMappingRound( p, p->pPars->nCutsMax - 1, 0, 0, "Start delay-2" );
p->pPars->fFancy = 0;
- delayDelay = If_ManDelayMax( p );
+ delayDelay = If_ManDelayMax( p, 0 );
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-delay mapping
If_ManPerformMappingRound( p, p->pPars->nCutsMax - 2, 0, 0, "Start flow" );
- delayPure = If_ManDelayMax( p );
+ delayPure = If_ManDelayMax( p, 0 );
if ( p->pPars->DelayTarget != -1 && delayPure < p->pPars->DelayTarget - p->fEpsilon )
delayPure = p->pPars->DelayTarget;
diff --git a/src/map/if/ifReduce.c b/src/map/if/ifReduce.c
index 69312c5b..3e3256c3 100644
--- a/src/map/if/ifReduce.c
+++ b/src/map/if/ifReduce.c
@@ -361,7 +361,7 @@ int If_ManImproveNodeFaninCompact0( If_Man_t * p, If_Obj_t * pObj, int nLimit, V
int i;
Vec_PtrForEachEntry( vFront, pFanin, i )
{
- if ( If_ObjIsPi(pFanin) )
+ if ( If_ObjIsCi(pFanin) )
continue;
if ( If_ManImproveNodeWillGrow(p, pFanin) )
continue;
@@ -391,7 +391,7 @@ int If_ManImproveNodeFaninCompact1( If_Man_t * p, If_Obj_t * pObj, int nLimit, V
int i;
Vec_PtrForEachEntry( vFront, pFanin, i )
{
- if ( If_ObjIsPi(pFanin) )
+ if ( If_ObjIsCi(pFanin) )
continue;
if ( If_ManImproveNodeFaninCost(p, pFanin) < 0 )
{
@@ -419,7 +419,7 @@ int If_ManImproveNodeFaninCompact2( If_Man_t * p, If_Obj_t * pObj, int nLimit, V
int i;
Vec_PtrForEachEntry( vFront, pFanin, i )
{
- if ( If_ObjIsPi(pFanin) )
+ if ( If_ObjIsCi(pFanin) )
continue;
if ( If_ManImproveNodeFaninCost(p, pFanin) <= 0 )
{
@@ -498,8 +498,8 @@ void If_ManImproveNodeReduce( If_Man_t * p, If_Obj_t * pObj, int nLimit )
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);
+ 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
diff --git a/src/map/if/ifSeq.c b/src/map/if/ifSeq.c
index ac2754c0..ddc74a49 100644
--- a/src/map/if/ifSeq.c
+++ b/src/map/if/ifSeq.c
@@ -24,9 +24,11 @@
/// 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 );
+static int If_ManBinarySearchPeriod( If_Man_t * p, int Mode );
+static int If_ManBinarySearch_rec( If_Man_t * p, int Mode, int FiMin, int FiMax );
+static int If_ManPerformMappingRoundSeq( If_Man_t * p, int Mode, int nIter, char * pLabel );
+static int If_ManPrepareMappingSeq( If_Man_t * p );
+static int If_ObjPerformMappingLatch( If_Man_t * p, If_Obj_t * pObj );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
@@ -45,46 +47,100 @@ static int If_ManMappingSeqConverged( If_Man_t * p );
***********************************************************************/
int If_ManPerformMappingSeq( If_Man_t * p )
{
- If_Obj_t * pObj, * pLatch;
- int i, clkTotal = clock();
- // set the number of cuts used
+ int PeriodBest, Mode = 0;
+
+ // collect nodes in the sequential order
+ If_ManPrepareMappingSeq( p );
+
+ // perform combinational mapping to get the upper bound on the clock period
+ If_ManPerformMappingRound( p, 2, 0, 0, NULL );
+ p->RequiredGlo = If_ManDelayMax( p, 0 );
+
+ // set parameters
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, NULL );
- p->pPars->fFancy = 0;
-
- // perform iterations over the circuit
- while ( !If_ManMappingSeqConverged( p ) )
+ p->nAttempts = 0;
+ p->nMaxIters = 50;
+ p->Period = (int)p->RequiredGlo;
+
+ // make sure the clock period words
+ if ( !If_ManBinarySearchPeriod( p, Mode ) )
{
- // 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 );
+ printf( "If_ManPerformMappingSeq(): The upper bound on the clock period cannot be computed.\n" );
+ return 0;
}
- if ( p->pPars->fVerbose )
+ // perform binary search
+ PeriodBest = If_ManBinarySearch_rec( p, Mode, 0, p->Period );
+
+ // recompute the best l-values
+ if ( p->Period != PeriodBest )
{
- PRT( "Total time", clock() - clkTotal );
+ p->Period = PeriodBest;
+ if ( !If_ManBinarySearchPeriod( p, Mode ) )
+ {
+ printf( "If_ManPerformMappingSeq(): The final clock period cannot be confirmed.\n" );
+ return 0;
+ }
}
+/*
+ // fix the problem with non-converged delays
+ If_ManForEachNode( p, pObj, i )
+ if ( pObj->LValue < -ABC_INFINITY/2 )
+ pObj->LValue = (float)0.0;
+ // write the retiming lags
+ p->vLags = Vec_IntStart( If_ManObjNum(p) + 1 );
+ If_ManForEachNode( p, pObj, i )
+ Vec_IntWriteEntry( vLags, i, Abc_NodeComputeLag(pObj->LValue, p->Period) );
+*/
+/*
+ // print the statistic into a file
+ {
+ FILE * pTable;
+ pTable = fopen( "a/seqmap__stats.txt", "a+" );
+ fprintf( pTable, "%d ", p->Period );
+ fprintf( pTable, "\n" );
+ fclose( pTable );
+ }
+*/
+ // print the result
+ if ( p->pPars->fLiftLeaves )
+ {
+// if ( p->pPars->fVerbose )
+ printf( "The best clock period is %3d. (Currently, network is not modified, so mapping will fail.)\n", p->Period );
+ return 0;
+ }
+// if ( p->pPars->fVerbose )
+ printf( "The best clock period is %3d.\n", p->Period );
return 1;
}
/**Function*************************************************************
- Synopsis [Performs sequential mapping.]
+ Synopsis [Performs binary search for the optimal clock period.]
+
+ Description [Assumes that FiMin is infeasible while FiMax is feasible.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManBinarySearch_rec( If_Man_t * p, int Mode, int FiMin, int FiMax )
+{
+ assert( FiMin < FiMax );
+ if ( FiMin + 1 == FiMax )
+ return FiMax;
+ // compute the median
+ p->Period = FiMin + (FiMax - FiMin)/2;
+ if ( If_ManBinarySearchPeriod( p, Mode ) )
+ return If_ManBinarySearch_rec( p, Mode, FiMin, p->Period ); // Median is feasible
+ else
+ return If_ManBinarySearch_rec( p, Mode, p->Period, FiMax ); // Median is infeasible
+}
+
+/**Function*************************************************************
+
+ Synopsis [Returns 1 if retiming with this clock period is feasible.]
Description []
@@ -93,16 +149,153 @@ int If_ManPerformMappingSeq( If_Man_t * p )
SeeAlso []
***********************************************************************/
-void If_CutLift( If_Cut_t * pCut )
+int If_ManBinarySearchPeriod( If_Man_t * p, int Mode )
{
- unsigned i;
- for ( i = 0; i < pCut->nLeaves; i++ )
- pCut->pLeaves[i] = ((pCut->pLeaves[i] >> 8) << 8) | ((pCut->pLeaves[i] & 255) + 1);
+ If_Obj_t * pObj;
+ int i, c, fConverged;
+ int fResetRefs = 0;
+
+ p->nAttempts++;
+
+ // set l-values of all nodes to be minus infinity, except PIs and constants
+ If_ManForEachObj( p, pObj, i )
+ {
+ pObj->nCuts = 1;
+ If_ObjSetLValue( pObj, -IF_FLOAT_LARGE );
+ if ( fResetRefs )
+ pObj->nRefs = 0;
+ }
+ If_ObjSetLValue( If_ManConst1(p), (float)0.0 );
+ If_ManForEachPi( p, pObj, i )
+ If_ObjSetLValue( pObj, (float)0.0 );
+
+ // reset references to their original state
+ if ( fResetRefs )
+ {
+ If_ManForEachObj( p, pObj, i )
+ {
+ if ( If_ObjIsCo(pObj) )
+ continue;
+ if ( pObj->pFanin0 ) pObj->pFanin0->nRefs++;
+ if ( pObj->pFanin1 ) pObj->pFanin1->nRefs++;
+ }
+ }
+
+ // update all values iteratively
+ fConverged = 0;
+ for ( c = 1; c <= p->nMaxIters; c++ )
+ {
+ if ( !If_ManPerformMappingRoundSeq( p, Mode, c, NULL ) )
+ {
+ fConverged = 1;
+ break;
+ }
+ p->RequiredGlo = If_ManDelayMax( p, 1 );
+ if ( p->RequiredGlo > p->Period + p->fEpsilon )
+ break;
+ }
+
+ // report the results
+ if ( p->pPars->fVerbose )
+ {
+ p->AreaGlo = p->pPars->fLiftLeaves? If_ManScanMappingSeq(p) : If_ManScanMapping(p);
+ printf( "Attempt = %2d. Iters = %3d. Area = %10.2f. Fi = %6.2f. ", p->nAttempts, c, p->AreaGlo, (float)p->Period );
+ if ( fConverged )
+ printf( " Feasible" );
+ else if ( c > p->nMaxIters )
+ printf( "Infeasible (timeout)" );
+ else
+ printf( "Infeasible" );
+ printf( "\n" );
+ }
+ return fConverged;
}
/**Function*************************************************************
- Synopsis [Performs sequential mapping.]
+ Synopsis [Performs one pass of l-value computation over all nodes.]
+
+ Description [Experimentally it was found that checking POs changes
+ is not enough to detect the convergence of l-values in the network.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManPerformMappingRoundSeq( If_Man_t * p, int Mode, int nIter, char * pLabel )
+{
+ ProgressBar * pProgress;
+ If_Obj_t * pObj;
+ int i, clk = clock();
+ int fVeryVerbose = 0;
+ int fChange = 0;
+ assert( Mode >= 0 && Mode <= 2 );
+ if ( !p->pPars->fVerbose )
+ pProgress = Extra_ProgressBarStart( stdout, If_ManObjNum(p) );
+ // map the internal nodes
+ p->nCutsMerged = 0;
+ If_ManForEachNode( p, pObj, i )
+ {
+ if ( !p->pPars->fVerbose )
+ Extra_ProgressBarUpdate( pProgress, i, pLabel );
+ // consider the camse of an AND gate
+ assert( If_ObjIsAnd(pObj) );
+ If_ObjPerformMappingAnd( p, pObj, Mode );
+ if ( pObj->fRepr )
+ If_ObjPerformMappingChoice( p, pObj, Mode );
+ // check if updating happens
+ if ( If_ObjLValue(pObj) < If_ObjCutBest(pObj)->Delay - p->fEpsilon )
+ {
+ If_ObjSetLValue( pObj, If_ObjCutBest(pObj)->Delay );
+ fChange = 1;
+ }
+//if ( If_ObjLValue(pObj) > -1000.0 )
+//printf( "Node %d %.2f ", pObj->Id, If_ObjLValue(pObj) );
+ }
+ if ( !p->pPars->fVerbose )
+ Extra_ProgressBarStop( pProgress );
+ // propagate arrival times from the registers
+ Vec_PtrForEachEntry( p->vLatchOrder, pObj, i )
+ fChange |= If_ObjPerformMappingLatch( p, pObj );
+//printf( "\n\n" );
+ // compute area and delay
+ if ( fVeryVerbose )
+ {
+ p->RequiredGlo = If_ManDelayMax( p, 1 );
+ p->AreaGlo = p->pPars->fLiftLeaves? If_ManScanMappingSeq(p) : If_ManScanMapping(p);
+ printf( "S%d: Fi = %6.2f. Del = %6.2f. Area = %8.2f. Cuts = %8d. Lim = %2d. Ave = %5.2f. ",
+ nIter, (float)p->Period, p->RequiredGlo, p->AreaGlo, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ PRT( "T", clock() - clk );
+ }
+ return fChange;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects latches in the topological order.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManCollectLatches_rec( If_Obj_t * pObj, Vec_Ptr_t * vLatches )
+{
+ if ( !If_ObjIsLatch(pObj) )
+ return;
+ if ( pObj->fMark )
+ return;
+ pObj->fMark = 1;
+ If_ManCollectLatches_rec( pObj->pFanin0, vLatches );
+ Vec_PtrPush( vLatches, pObj );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collects latches in the topological order.]
Description []
@@ -111,19 +304,25 @@ void If_CutLift( If_Cut_t * pCut )
SeeAlso []
***********************************************************************/
-void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch )
+Vec_Ptr_t * If_ManCollectLatches( If_Man_t * p )
{
- 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 );
+ Vec_Ptr_t * vLatches;
+ If_Obj_t * pObj;
+ int i;
+ // collect latches
+ vLatches = Vec_PtrAlloc( p->pPars->nLatches );
+ Vec_PtrForEachEntryStart( p->vCis, pObj, i, If_ManCiNum(p) - p->pPars->nLatches )
+ If_ManCollectLatches_rec( pObj, vLatches );
+ // clean marks
+ Vec_PtrForEachEntry( vLatches, pObj, i )
+ pObj->fMark = 0;
+ assert( Vec_PtrSize(vLatches) == p->pPars->nLatches );
+ return vLatches;
}
/**Function*************************************************************
- Synopsis [Performs sequential mapping.]
+ Synopsis [Prepares for sequential mapping by linking the latches.]
Description []
@@ -132,23 +331,43 @@ void If_ObjPerformMappingLI( If_Man_t * p, If_Obj_t * pLatch )
SeeAlso []
***********************************************************************/
-void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj )
+int If_ManPrepareMappingSeq( If_Man_t * p )
{
+ If_Obj_t * pObj, * pObjLi, * pObjLo, * pTemp;
If_Cut_t * pCut;
- int c, Limit = IF_MIN( p->nCuts + 1, p->nCutsUsed );
- assert( If_ObjIsPo(pLatch) );
- for ( c = 1; c < Limit; c++ )
+ int i;
+ // link the latch outputs (PIs) directly to the drivers of latch inputs (POs)
+ for ( i = 0; i < p->pPars->nLatches; i++ )
+ {
+ pObjLo = If_ManCi( p, If_ManCiNum(p) - p->pPars->nLatches + i );
+ pObjLi = If_ManCo( p, If_ManCoNum(p) - p->pPars->nLatches + i );
+ pObjLo->pFanin0 = If_ObjFanin0( pObjLi );
+ pObjLo->fCompl0 = If_ObjFaninC0( pObjLi );
+// pObjLo->pFanin0 = pObjLi;
+ }
+ // collect latches
+ p->vLatchOrder = If_ManCollectLatches( p );
+ // propagate elementary cuts
+ if ( p->pPars->fLiftLeaves )
{
- pCut = pObj->Cuts + c;
- If_CutCopy( pCut, pLatch->Cuts + c - 1 );
- If_CutLift( pCut );
- pCut->Delay -= p->Fi;
+ Vec_PtrForEachEntry( p->vLatchOrder, pObj, i )
+ {
+ pCut = If_ObjCutTriv(pObj);
+ If_CutCopy( pCut, If_ObjFanin0(pObj)->Cuts );
+ If_CutLift( pCut );
+ pCut->Delay -= p->Period;
+ pCut->fCompl ^= pObj->fCompl0;
+
+ pTemp = If_ManObj(p, pCut->pLeaves[0] >> 8);
+ assert( !If_ObjIsLatch(pTemp) );
+ }
}
+ return 1;
}
/**Function*************************************************************
- Synopsis [Performs sequential mapping.]
+ Synopsis [Performs mapping of the latches.]
Description []
@@ -157,12 +376,36 @@ void If_ObjPerformMappingLO( If_Man_t * p, If_Obj_t * pLatch, If_Obj_t * pObj )
SeeAlso []
***********************************************************************/
-int If_ManMappingSeqConverged( If_Man_t * p )
+int If_ObjPerformMappingLatch( If_Man_t * p, If_Obj_t * pObj )
{
- return 0;
+ If_Obj_t * pFanin;
+ If_Cut_t * pCut;
+ float LValueOld;
+ int i;
+ assert( If_ObjIsLatch(pObj) );
+ // save old l-value
+ LValueOld = If_ObjLValue(pObj);
+ pFanin = If_ObjFanin0(pObj);
+ assert( pFanin->nCuts > 0 );
+ if ( !p->pPars->fLiftLeaves )
+ {
+ pObj->nCuts = 1;
+ If_ObjSetLValue( pObj, If_ObjLValue(pFanin) - p->Period );
+ }
+ else
+ {
+ pObj->nCuts = pFanin->nCuts;
+ If_ObjForEachCut( pObj, pCut, i )
+ {
+ If_CutCopy( pCut, pFanin->Cuts + i );
+ If_CutLift( pCut );
+ pCut->Delay -= p->Period;
+ pCut->fCompl ^= pObj->fCompl0;
+ }
+ }
+ return LValueOld != If_ObjLValue(pObj);
}
-
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
diff --git a/src/map/if/ifLib.c b/src/map/if/ifTime.c
index 85747b8e..f0041868 100644
--- a/src/map/if/ifLib.c
+++ b/src/map/if/ifTime.c
@@ -1,12 +1,12 @@
/**CFile****************************************************************
- FileName [ifLib.c]
+ FileName [ifTime.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [FPGA mapping based on priority cuts.]
- Synopsis [Computation of LUT paramters depending on the library.]
+ Synopsis [Computation of delay paramters depending on the library.]
Author [Alan Mishchenko]
@@ -14,7 +14,7 @@
Date [Ver. 1.0. Started - November 21, 2006.]
- Revision [$Id: ifLib.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
+ Revision [$Id: ifTime.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
***********************************************************************/
@@ -48,11 +48,12 @@ float If_CutDelay( If_Man_t * p, If_Cut_t * pCut )
If_Obj_t * pLeaf;
float Delay, DelayCur;
float * pLutDelays;
- int i;
- assert( pCut->nLeaves > 1 );
+ int i, Shift;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
Delay = -IF_FLOAT_LARGE;
if ( p->pPars->pLutLib )
{
+ assert( !p->pPars->fLiftLeaves );
pLutDelays = p->pPars->pLutLib->pLutDelays[pCut->nLeaves];
if ( p->pPars->pLutLib->fVarPinDelays )
{
@@ -77,6 +78,7 @@ float If_CutDelay( If_Man_t * p, If_Cut_t * pCut )
{
if ( pCut->fUser )
{
+ assert( !p->pPars->fLiftLeaves );
If_CutForEachLeaf( p, pCut, pLeaf, i )
{
DelayCur = If_ObjCutBest(pLeaf)->Delay + (float)pCut->pPerm[i];
@@ -85,10 +87,21 @@ float If_CutDelay( If_Man_t * p, If_Cut_t * pCut )
}
else
{
- If_CutForEachLeaf( p, pCut, pLeaf, i )
+ if ( p->pPars->fLiftLeaves )
{
- DelayCur = If_ObjCutBest(pLeaf)->Delay;
- Delay = IF_MAX( Delay, DelayCur );
+ If_CutForEachLeafSeq( p, pCut, pLeaf, Shift, i )
+ {
+ DelayCur = If_ObjCutBest(pLeaf)->Delay - Shift * p->Period;
+ Delay = IF_MAX( Delay, DelayCur );
+ }
+ }
+ else
+ {
+ If_CutForEachLeaf( p, pCut, pLeaf, i )
+ {
+ DelayCur = If_ObjCutBest(pLeaf)->Delay;
+ Delay = IF_MAX( Delay, DelayCur );
+ }
}
Delay += 1.0;
}
@@ -115,6 +128,7 @@ void If_CutPropagateRequired( If_Man_t * p, If_Cut_t * pCut, float ObjRequired )
float * pLutDelays;
float Required;
int i;
+ assert( !p->pPars->fLiftLeaves );
// compute the pins
if ( p->pPars->pLutLib )
{
diff --git a/src/map/if/ifUtil.c b/src/map/if/ifUtil.c
index bb8e3dee..4b136f55 100644
--- a/src/map/if/ifUtil.c
+++ b/src/map/if/ifUtil.c
@@ -30,6 +30,65 @@
/**Function*************************************************************
+ Synopsis [Sets all the node copy to NULL.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManCleanNodeCopy( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i;
+ If_ManForEachObj( p, pObj, i )
+ If_ObjSetCopy( pObj, NULL );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sets all the cut data to NULL.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManCleanCutData( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ If_Cut_t * pCut;
+ int i, k;
+ If_ManForEachObj( p, pObj, i )
+ If_ObjForEachCut( pObj, pCut, k )
+ If_CutSetData( pCut, NULL );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Sets all visited marks to 0.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManCleanMarkV( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i;
+ If_ManForEachObj( p, pObj, i )
+ pObj->fVisit = 0;
+}
+
+/**Function*************************************************************
+
Synopsis [Returns the max delay of the POs.]
Description []
@@ -39,7 +98,7 @@
SeeAlso []
***********************************************************************/
-float If_ManDelayMax( If_Man_t * p )
+float If_ManDelayMax( If_Man_t * p, int fSeq )
{
If_Obj_t * pObj;
float DelayBest;
@@ -50,15 +109,22 @@ float If_ManDelayMax( If_Man_t * p )
p->pPars->fLatchPaths = 0;
}
DelayBest = -IF_FLOAT_LARGE;
- if ( p->pPars->fLatchPaths )
+ if ( fSeq )
+ {
+ assert( p->pPars->nLatches > 0 );
+ If_ManForEachPo( p, pObj, i )
+ if ( DelayBest < If_ObjCutBest( If_ObjFanin0(pObj) )->Delay )
+ DelayBest = If_ObjCutBest( If_ObjFanin0(pObj) )->Delay;
+ }
+ else if ( p->pPars->fLatchPaths )
{
If_ManForEachLatch( p, pObj, i )
if ( DelayBest < If_ObjCutBest( If_ObjFanin0(pObj) )->Delay )
DelayBest = If_ObjCutBest( If_ObjFanin0(pObj) )->Delay;
}
- else
+ else
{
- If_ManForEachPo( p, pObj, i )
+ If_ManForEachCo( p, pObj, i )
if ( DelayBest < If_ObjCutBest( If_ObjFanin0(pObj) )->Delay )
DelayBest = If_ObjCutBest( If_ObjFanin0(pObj) )->Delay;
}
@@ -67,7 +133,7 @@ float If_ManDelayMax( If_Man_t * p )
/**Function*************************************************************
- Synopsis [Sets all the node copy to NULL.]
+ Synopsis [Computes the required times of all nodes.]
Description []
@@ -76,33 +142,43 @@ float If_ManDelayMax( If_Man_t * p )
SeeAlso []
***********************************************************************/
-void If_ManCleanNodeCopy( If_Man_t * p )
+void If_ManComputeRequired( If_Man_t * p, int fFirstTime )
{
If_Obj_t * pObj;
int i;
- If_ManForEachObj( p, pObj, i )
- If_ObjSetCopy( pObj, NULL );
-}
-
-/**Function*************************************************************
-
- Synopsis [Sets all the cut data to NULL.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void If_ManCleanCutData( If_Man_t * p )
-{
- If_Obj_t * pObj;
- If_Cut_t * pCut;
- int i, k;
- If_ManForEachObj( p, pObj, i )
- If_ObjForEachCut( pObj, pCut, k )
- If_CutSetData( pCut, NULL );
+ // compute area, clean required times, collect nodes used in the mapping
+ p->AreaGlo = If_ManScanMapping( p );
+ // get the global required times
+ p->RequiredGlo = If_ManDelayMax( p, 0 );
+ // update the required times according to the target
+ if ( p->pPars->DelayTarget != -1 )
+ {
+ if ( p->RequiredGlo > p->pPars->DelayTarget + p->fEpsilon )
+ {
+ if ( fFirstTime )
+ printf( "Cannot meet the target required times (%4.2f). Mapping continues anyway.\n", p->pPars->DelayTarget );
+ }
+ else if ( p->RequiredGlo < p->pPars->DelayTarget - p->fEpsilon )
+ {
+ if ( fFirstTime )
+ printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->RequiredGlo, p->pPars->DelayTarget );
+ p->RequiredGlo = p->pPars->DelayTarget;
+ }
+ }
+ // set the required times for the POs
+ if ( p->pPars->fLatchPaths )
+ {
+ If_ManForEachLatch( p, pObj, i )
+ If_ObjFanin0(pObj)->Required = p->RequiredGlo;
+ }
+ else
+ {
+ If_ManForEachCo( p, pObj, i )
+ If_ObjFanin0(pObj)->Required = p->RequiredGlo;
+ }
+ // go through the nodes in the reverse topological order
+ Vec_PtrForEachEntry( p->vMapped, pObj, i )
+ If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required );
}
/**Function*************************************************************
@@ -122,7 +198,7 @@ float If_ManScanMapping_rec( If_Man_t * p, If_Obj_t * pObj, If_Obj_t ** ppStore
If_Cut_t * pCutBest;
float aArea;
int i;
- if ( pObj->nRefs++ || If_ObjIsPi(pObj) || If_ObjIsConst1(pObj) )
+ if ( pObj->nRefs++ || If_ObjIsCi(pObj) || If_ObjIsConst1(pObj) )
return 0.0;
// store the node in the structure by level
assert( If_ObjIsAnd(pObj) );
@@ -153,6 +229,7 @@ float If_ManScanMapping( If_Man_t * p )
If_Obj_t * pObj, ** ppStore;
float aArea;
int i;
+ assert( !p->pPars->fLiftLeaves );
// clean all references
If_ManForEachObj( p, pObj, i )
{
@@ -164,7 +241,7 @@ float If_ManScanMapping( If_Man_t * p )
memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) );
// collect nodes reachable from POs in the DFS order through the best cuts
aArea = 0;
- If_ManForEachPo( p, pObj, i )
+ If_ManForEachCo( p, pObj, i )
aArea += If_ManScanMapping_rec( p, If_ObjFanin0(pObj), ppStore );
// reconnect the nodes in reverse topological order
Vec_PtrClear( p->vMapped );
@@ -177,7 +254,7 @@ float If_ManScanMapping( If_Man_t * p )
/**Function*************************************************************
- Synopsis [Computes the required times of all nodes.]
+ Synopsis [Computes area, references, and nodes used in the mapping.]
Description []
@@ -186,46 +263,55 @@ float If_ManScanMapping( If_Man_t * p )
SeeAlso []
***********************************************************************/
-void If_ManComputeRequired( If_Man_t * p, int fFirstTime )
+float If_ManScanMappingSeq_rec( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vMapped )
+{
+ If_Obj_t * pLeaf;
+ If_Cut_t * pCutBest;
+ float aArea;
+ int i, Shift;
+ if ( pObj->nRefs++ || If_ObjIsCi(pObj) || If_ObjIsConst1(pObj) )
+ return 0.0;
+ // store the node in the structure by level
+ assert( If_ObjIsAnd(pObj) );
+ // visit the transitive fanin of the selected cut
+ pCutBest = If_ObjCutBest(pObj);
+ aArea = If_ObjIsAnd(pObj)? If_CutLutArea(p, pCutBest) : (float)0.0;
+ If_CutForEachLeafSeq( p, pCutBest, pLeaf, Shift, i )
+ aArea += If_ManScanMappingSeq_rec( p, pLeaf, vMapped );
+ // add the node
+ Vec_PtrPush( vMapped, pObj );
+ return aArea;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes area, references, and nodes used in the mapping.]
+
+ Description [Collects the nodes in reverse topological order in array
+ p->vMapping.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+float If_ManScanMappingSeq( If_Man_t * p )
{
If_Obj_t * pObj;
+ float aArea;
int i;
- // compute area, clean required times, collect nodes used in the mapping
- p->AreaGlo = If_ManScanMapping( p );
- // get the global required times
- p->RequiredGlo = If_ManDelayMax( p );
- // update the required times according to the target
- if ( p->pPars->DelayTarget != -1 )
- {
- if ( p->RequiredGlo > p->pPars->DelayTarget + p->fEpsilon )
- {
- if ( fFirstTime )
- printf( "Cannot meet the target required times (%4.2f). Mapping continues anyway.\n", p->pPars->DelayTarget );
- }
- else if ( p->RequiredGlo < p->pPars->DelayTarget - p->fEpsilon )
- {
- if ( fFirstTime )
- printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->RequiredGlo, p->pPars->DelayTarget );
- p->RequiredGlo = p->pPars->DelayTarget;
- }
- }
- // set the required times for the POs
- if ( p->pPars->fLatchPaths )
- {
- If_ManForEachLatch( p, pObj, i )
- If_ObjFanin0(pObj)->Required = p->RequiredGlo;
- }
- else
- {
- If_ManForEachPo( p, pObj, i )
- If_ObjFanin0(pObj)->Required = p->RequiredGlo;
- }
- // go through the nodes in the reverse topological order
- Vec_PtrForEachEntry( p->vMapped, pObj, i )
- If_CutPropagateRequired( p, If_ObjCutBest(pObj), pObj->Required );
+ assert( p->pPars->fLiftLeaves );
+ // clean all references
+ If_ManForEachObj( p, pObj, i )
+ pObj->nRefs = 0;
+ // collect nodes reachable from POs in the DFS order through the best cuts
+ aArea = 0;
+ Vec_PtrClear( p->vMapped );
+ If_ManForEachPo( p, pObj, i )
+ aArea += If_ManScanMappingSeq_rec( p, If_ObjFanin0(pObj), p->vMapped );
+ return aArea;
}
-
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
diff --git a/src/map/if/module.make b/src/map/if/module.make
index 20586ed8..c4fa56cb 100644
--- a/src/map/if/module.make
+++ b/src/map/if/module.make
@@ -1,10 +1,10 @@
SRC += src/map/if/ifCore.c \
src/map/if/ifCut.c \
- src/map/if/ifLib.c \
src/map/if/ifMan.c \
src/map/if/ifMap.c \
src/map/if/ifPrepro.c \
src/map/if/ifReduce.c \
src/map/if/ifSeq.c \
+ src/map/if/ifTime.c \
src/map/if/ifTruth.c \
src/map/if/ifUtil.c