diff options
Diffstat (limited to 'src/map')
| -rw-r--r-- | src/map/if/if.h | 101 | ||||
| -rw-r--r-- | src/map/if/ifCore.c | 18 | ||||
| -rw-r--r-- | src/map/if/ifCut.c | 33 | ||||
| -rw-r--r-- | src/map/if/ifMan.c | 28 | ||||
| -rw-r--r-- | src/map/if/ifMap.c | 58 | ||||
| -rw-r--r-- | src/map/if/ifPrepro.c | 6 | ||||
| -rw-r--r-- | src/map/if/ifReduce.c | 10 | ||||
| -rw-r--r-- | src/map/if/ifSeq.c | 357 | ||||
| -rw-r--r-- | src/map/if/ifTime.c (renamed from src/map/if/ifLib.c) | 30 | ||||
| -rw-r--r-- | src/map/if/ifUtil.c | 220 | ||||
| -rw-r--r-- | src/map/if/module.make | 2 |
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 |