summaryrefslogtreecommitdiffstats
path: root/src/map/if
diff options
context:
space:
mode:
authorAlan Mishchenko <alanmi@berkeley.edu>2007-02-25 08:01:00 -0800
committerAlan Mishchenko <alanmi@berkeley.edu>2007-02-25 08:01:00 -0800
commit81fae91a95b8b51d7a10d3884df92dc89eb266bf (patch)
tree504f7581908335369a15d97653ba2bb3fec31d08 /src/map/if
parentfb51057e4a36d2e5737bba8739b88140b55db7c7 (diff)
downloadabc-81fae91a95b8b51d7a10d3884df92dc89eb266bf.tar.gz
abc-81fae91a95b8b51d7a10d3884df92dc89eb266bf.tar.bz2
abc-81fae91a95b8b51d7a10d3884df92dc89eb266bf.zip
Version abc70225
Diffstat (limited to 'src/map/if')
-rw-r--r--src/map/if/if.h120
-rw-r--r--src/map/if/ifCore.c78
-rw-r--r--src/map/if/ifCut.c145
-rw-r--r--src/map/if/ifMan.c336
-rw-r--r--src/map/if/ifMap.c192
-rw-r--r--src/map/if/ifPrepro.c175
-rw-r--r--src/map/if/ifReduce.c16
-rw-r--r--src/map/if/ifSeq.c448
-rw-r--r--src/map/if/ifUtil.c171
-rw-r--r--src/map/if/module.make1
10 files changed, 968 insertions, 714 deletions
diff --git a/src/map/if/if.h b/src/map/if/if.h
index 81d4007c..7e22707f 100644
--- a/src/map/if/if.h
+++ b/src/map/if/if.h
@@ -46,7 +46,9 @@ extern "C" {
// the largest possible number of LUT inputs when funtionality of the LUTs are computed
#define IF_MAX_FUNC_LUTSIZE 15
// a very large number
-#define IF_INFINITY 100000000
+#define IF_INFINITY 100000000
+// the largest possible user cut cost
+#define IF_COST_MAX ((1<<14)-1)
// object types
typedef enum {
@@ -55,10 +57,7 @@ typedef enum {
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
- IF_BOX, // 7: box
- IF_VOID // 8: unused object
+ IF_VOID // 5: unused object
} If_Type_t;
////////////////////////////////////////////////////////////////////////
@@ -70,6 +69,7 @@ typedef struct If_Par_t_ If_Par_t;
typedef struct If_Lib_t_ If_Lib_t;
typedef struct If_Obj_t_ If_Obj_t;
typedef struct If_Cut_t_ If_Cut_t;
+typedef struct If_Set_t_ If_Set_t;
// parameters
struct If_Par_t_
@@ -88,11 +88,13 @@ struct If_Par_t_
int fSeqMap; // sequential mapping
int fVerbose; // the verbosity flag
// internal parameters
+ int fAreaOnly; // area only mode
int fTruth; // truth table computation enabled
int fUsePerm; // use permutation (delay info)
- int fUseBdds; // sets local BDDs at the nodes
- int fUseSops; // sets local SOPs at the nodes
- int fUseCnfs; // sets local CNFs at the nodes
+ int fUseBdds; // use local BDDs as a cost function
+ int fUseSops; // use local SOPs as a cost function
+ int fUseCnfs; // use local CNFs as a cost function
+ int fUseMv; // use local MV-SOPs as a cost function
int nLatches; // the number of latches in seq mapping
int fLiftLeaves; // shift the leaves for seq mapping
If_Lib_t * pLutLib; // the LUT library
@@ -129,11 +131,14 @@ struct If_Man_t_
int nLevelMax; // the max number of AIG levels
float fEpsilon; // epsilon used for comparison
float RequiredGlo; // global required times
+ float RequiredGlo2; // global required times
float AreaGlo; // global area
int nNets; // the sum total of fanins of all LUTs in the mapping
int nCutsUsed; // the number of cuts currently used
int nCutsMerged; // the total number of cuts merged
unsigned * puTemp[4]; // used for the truth table computation
+ int SortMode; // one of the three sorting modes
+ int fNextRound; // set to 1 after the first round
// sequential mapping
Vec_Ptr_t * vLatchOrder; // topological ordering of latches
Vec_Int_t * vLags; // sequentail lags of all nodes
@@ -141,15 +146,16 @@ struct If_Man_t_
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
- int nEntryBase; // the size of the entry minus cut leaf arrays
- int nTruthSize; // the size of the truth table if allocated
- int nPermSize; // the size of the permutation array (in words)
- int nCutSize; // the size of the cut
- // temporary cut storage
- int nCuts; // the number of cuts used
- If_Cut_t ** ppCuts; // the storage space for cuts
+ int nTruthWords; // the size of the truth table if allocated
+ int nPermWords; // the size of the permutation array (in words)
+ int nObjBytes; // the size of the object
+ int nCutBytes; // the size of the cut
+ int nSetBytes; // the size of the cut set
+ Mem_Fixed_t * pMemObj; // memory manager for objects (entrysize = nEntrySize)
+ Mem_Fixed_t * pMemSet; // memory manager for sets of cuts (entrysize = nCutSize*(nCutsMax+1))
+ If_Set_t * pMemCi; // memory for CI cutsets
+ If_Set_t * pMemAnd; // memory for AND cutsets
+ If_Set_t * pFreeList; // the list of free cutsets
};
// priority cut
@@ -169,6 +175,15 @@ struct If_Cut_t_
unsigned * pTruth; // the truth table
};
+// set of priority cut
+struct If_Set_t_
+{
+ short nCutsMax; // the max number of cuts
+ short nCuts; // the current number of cuts
+ If_Set_t * pNext; // next cutset in the free list
+ If_Cut_t ** ppCuts; // the array of pointers to the cuts
+};
+
// node extension
struct If_Obj_t_
{
@@ -182,36 +197,37 @@ struct If_Obj_t_
unsigned Level : 22; // logic level of the node
int Id; // integer ID
int nRefs; // the number of references
- int nCuts; // the number of cuts
+ int nVisits; // the number of visits to this node
+ int nVisitsCopy; // the number of visits to this node
If_Obj_t * pFanin0; // the first fanin
If_Obj_t * pFanin1; // the second fanin
If_Obj_t * pEquiv; // the choice node
float EstRefs; // estimated reference counter
float Required; // required time of the onde
- void * pCopy; // used for duplication
- If_Cut_t Cuts[0]; // the cuts of the node
+ float LValue; // sequential arrival time of the node
+ void * pCopy; // used for object duplication
+ If_Set_t * pCutSet; // the pointer to the cutset
+ If_Cut_t CutBest; // the best cut selected
};
-static inline If_Obj_t * If_ManConst1( If_Man_t * p ) { return p->pConst1; }
-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_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 If_Obj_t * If_ManConst1( If_Man_t * p ) { return p->pConst1; }
+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_ManLi( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCos, If_ManCoNum(p) - p->pPars->nLatches + i ); }
+static inline If_Obj_t * If_ManLo( If_Man_t * p, int i ) { return (If_Obj_t *)Vec_PtrEntry( p->vCis, If_ManCiNum(p) - p->pPars->nLatches + 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 int If_ObjIsConst1( If_Obj_t * pObj ) { return pObj->Type == IF_CONST1; }
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; }
-static inline int If_ObjIsBox( If_Obj_t * pObj ) { return pObj->Type == IF_BOX; }
static inline If_Obj_t * If_ObjFanin0( If_Obj_t * pObj ) { return pObj->pFanin0; }
static inline If_Obj_t * If_ObjFanin1( If_Obj_t * pObj ) { return pObj->pFanin1; }
@@ -221,13 +237,14 @@ static inline void * If_ObjCopy( If_Obj_t * pObj ) { r
static inline void If_ObjSetCopy( If_Obj_t * pObj, void * pCopy ) { pObj->pCopy = pCopy; }
static inline void If_ObjSetChoice( If_Obj_t * pObj, If_Obj_t * pEqu ) { pObj->pEquiv = pEqu; }
-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 + (int)(pObj->nCuts > 1); }
+static inline If_Cut_t * If_ObjCutBest( If_Obj_t * pObj ) { return &pObj->CutBest; }
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 float If_ObjArrTime( If_Obj_t * pObj ) { return If_ObjCutBest(pObj)->Delay; }
+static inline void If_ObjSetArrTime( If_Obj_t * pObj, float ArrTime ) { If_ObjCutBest(pObj)->Delay = ArrTime; }
+
+static inline float If_ObjLValue( If_Obj_t * pObj ) { return pObj->LValue; }
+static inline void If_ObjSetLValue( If_Obj_t * pObj, float LValue ) { pObj->LValue = 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; }
@@ -264,20 +281,19 @@ static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { r
#define If_ManForEachPo( p, pObj, i ) \
Vec_PtrForEachEntryStop( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches )
// iterator over the latches
-#define If_ManForEachLatch( p, pObj, i ) \
+#define If_ManForEachLatchInput( p, pObj, i ) \
Vec_PtrForEachEntryStart( p->vCos, pObj, i, If_ManCoNum(p) - p->pPars->nLatches )
+#define If_ManForEachLatchOutput( p, pObj, i ) \
+ Vec_PtrForEachEntryStart( p->vCis, pObj, i, If_ManCiNum(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 )
-// iterator over logic nodes (AND and EXOR gates)
+// iterator over logic nodes
#define If_ManForEachNode( p, pObj, i ) \
If_ManForEachObj( p, pObj, i ) if ( pObj->Type != IF_AND ) {} else
// iterator over cuts of the node
#define If_ObjForEachCut( pObj, pCut, i ) \
- for ( i = 0; (i < (int)(pObj)->nCuts) && ((pCut) = (pObj)->Cuts + i); i++ )
-// 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++ )
+ for ( i = 0; (i < (pObj)->pCutSet->nCuts) && ((pCut) = (pObj)->pCutSet->ppCuts[i]); i++ )
// 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++ )
@@ -295,6 +311,7 @@ static inline float If_CutLutArea( If_Man_t * p, If_Cut_t * pCut ) { r
/*=== ifCore.c ===========================================================*/
extern int If_ManPerformMapping( If_Man_t * p );
+extern int If_ManPerformMappingComb( If_Man_t * p );
/*=== 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 );
@@ -304,10 +321,11 @@ extern void If_CutPrint( If_Man_t * p, If_Cut_t * pCut );
extern void If_CutPrintTiming( If_Man_t * p, If_Cut_t * pCut );
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_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut );
+extern void If_CutSort( If_Man_t * p, If_Set_t * pCutSet, 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_CutCopy( If_Man_t * p, If_Cut_t * pCutDest, If_Cut_t * pCutSrc );
extern void If_ManSortCuts( If_Man_t * p, int Mode );
/*=== ifMan.c =============================================================*/
extern If_Man_t * If_ManStart( If_Par_t * pPars );
@@ -316,12 +334,16 @@ 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 );
+extern void If_ManSetupCutTriv( If_Man_t * p, If_Cut_t * pCut, int ObjId );
+extern void If_ManSetupCiCutSets( If_Man_t * p );
+extern If_Set_t * If_ManSetupNodeCutSet( If_Man_t * p, If_Obj_t * pObj );
+extern void If_ManDerefNodeCutSet( If_Man_t * p, If_Obj_t * pObj );
+extern void If_ManDerefChoiceCutSet( If_Man_t * p, If_Obj_t * pObj );
+extern void If_ManSetupSetAll( If_Man_t * p );
/*=== 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 );
+extern void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess );
+extern void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess );
+extern int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fPreprocess, char * pLabel );
/*=== ifReduce.c ==========================================================*/
extern void If_ManImproveMapping( If_Man_t * p );
/*=== ifSeq.c =============================================================*/
@@ -336,9 +358,11 @@ 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 void If_ManComputeRequired( If_Man_t * p );
extern float If_ManScanMapping( If_Man_t * p );
extern float If_ManScanMappingSeq( If_Man_t * p );
+extern void If_ManResetOriginalRefs( If_Man_t * p );
+extern int If_ManCrossCut( If_Man_t * p );
#ifdef __cplusplus
}
diff --git a/src/map/if/ifCore.c b/src/map/if/ifCore.c
index be2c7e33..60ddcbe1 100644
--- a/src/map/if/ifCore.c
+++ b/src/map/if/ifCore.c
@@ -41,54 +41,98 @@
***********************************************************************/
int If_ManPerformMapping( If_Man_t * p )
{
- If_Obj_t * pObj;
- int clkTotal = clock();
- int RetValue, i;
+ p->pPars->fAreaOnly = p->pPars->fArea; // temporary
+
+ // create the CI cutsets
+ If_ManSetupCiCutSets( p );
+ // allocate memory for other cutsets
+ If_ManSetupSetAll( p );
// try sequential mapping
if ( p->pPars->fSeqMap )
{
+ int RetValue;
+// printf( "Currently sequential mapping is not performed.\n" );
RetValue = If_ManPerformMappingSeq( p );
- if ( p->pPars->fVerbose )
- {
- PRT( "Total time", clock() - clkTotal );
- }
return RetValue;
+// return 1;
}
- // set arrival times and trivial cuts at const 1 and PIs
- If_ManConst1(p)->Cuts[0].Delay = 0.0;
- If_ManForEachCi( p, pObj, i )
- pObj->Cuts[0].Delay = p->pPars->pTimesArr[i];
- // set the fanout estimates of the PIs
+ return If_ManPerformMappingComb( p );
+}
+
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManPerformMappingComb( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int clkTotal = clock();
+ int i;
+
+ // set arrival times and fanout estimates
If_ManForEachCi( p, pObj, i )
+ {
+ If_ObjSetArrTime( pObj, p->pPars->pTimesArr[i] );
pObj->EstRefs = (float)1.0;
+ }
+
// delay oriented mapping
- if ( p->pPars->fPreprocess && !p->pPars->fArea && p->pPars->nCutsMax >= 4 )
- If_ManPerformMappingPreprocess( p );
- else
+ if ( p->pPars->fPreprocess && !p->pPars->fArea )
+ {
+ // map for delay
If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1, "Delay" );
+ // map for delay second option
+ p->pPars->fFancy = 1;
+ If_ManResetOriginalRefs( p );
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1, "Delay-2" );
+ p->pPars->fFancy = 0;
+ // map for area
+ p->pPars->fArea = 1;
+ If_ManResetOriginalRefs( p );
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 1, "Area" );
+ p->pPars->fArea = 0;
+ }
+ else
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 0, "Delay" );
+
// try to improve area by expanding and reducing the cuts
if ( p->pPars->fExpRed && !p->pPars->fTruth )
If_ManImproveMapping( p );
+
// area flow oriented mapping
for ( i = 0; i < p->pPars->nFlowIters; i++ )
{
- If_ManPerformMappingRound( p, p->pPars->nCutsMax, 1, 1, "Flow" );
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 1, 0, "Flow" );
if ( p->pPars->fExpRed && !p->pPars->fTruth )
If_ManImproveMapping( p );
}
+
// area oriented mapping
for ( i = 0; i < p->pPars->nAreaIters; i++ )
{
- If_ManPerformMappingRound( p, p->pPars->nCutsMax, 2, 1, "Area" );
+ If_ManPerformMappingRound( p, p->pPars->nCutsMax, 2, 0, "Area" );
if ( p->pPars->fExpRed && !p->pPars->fTruth )
If_ManImproveMapping( p );
}
+
if ( p->pPars->fVerbose )
{
+// printf( "Total memory = %7.2f Mb. Peak cut memory = %7.2f Mb. ",
+// 1.0 * (p->nObjBytes + 2*sizeof(void *)) * If_ManObjNum(p) / (1<<20),
+// 1.0 * p->nSetBytes * Mem_FixedReadMaxEntriesUsed(p->pMemSet) / (1<<20) );
PRT( "Total time", clock() - clkTotal );
}
+// printf( "Cross cut memory = %d.\n", Mem_FixedReadMaxEntriesUsed(p->pMemSet) );
return 1;
}
diff --git a/src/map/if/ifCut.c b/src/map/if/ifCut.c
index f0663f7f..57dd2c41 100644
--- a/src/map/if/ifCut.c
+++ b/src/map/if/ifCut.c
@@ -87,13 +87,14 @@ static inline int If_CutCheckEquality( If_Cut_t * pDom, If_Cut_t * pCut )
SeeAlso []
***********************************************************************/
-int If_CutFilter( If_Man_t * p, If_Cut_t * pCut )
-{
+int If_CutFilter( If_Set_t * pCutSet, If_Cut_t * pCut )
+{
If_Cut_t * pTemp;
- int i;
- for ( i = 0; i < p->nCuts; i++ )
+ int i, k;
+ assert( pCutSet->ppCuts[pCutSet->nCuts] == pCut );
+ for ( i = 0; i < pCutSet->nCuts; i++ )
{
- pTemp = p->ppCuts[i];
+ pTemp = pCutSet->ppCuts[i];
if ( pTemp->nLeaves > pCut->nLeaves )
{
// do not fiter the first cut
@@ -105,10 +106,15 @@ int If_CutFilter( If_Man_t * p, If_Cut_t * pCut )
// check containment seriously
if ( If_CutCheckDominance( pCut, pTemp ) )
{
- // removed contained cut
- p->ppCuts[i] = p->ppCuts[p->nCuts-1];
- p->ppCuts[p->nCuts-1] = pTemp;
- p->nCuts--;
+// p->ppCuts[i] = p->ppCuts[p->nCuts-1];
+// p->ppCuts[p->nCuts-1] = pTemp;
+// p->nCuts--;
+// i--;
+ // remove contained cut
+ for ( k = i; k < pCutSet->nCuts; k++ )
+ pCutSet->ppCuts[k] = pCutSet->ppCuts[k+1];
+ pCutSet->ppCuts[pCutSet->nCuts] = pTemp;
+ pCutSet->nCuts--;
i--;
}
}
@@ -290,6 +296,7 @@ int If_CutMerge( If_Cut_t * pCut0, If_Cut_t * pCut1, If_Cut_t * pCut )
if ( !If_CutMergeOrdered( pCut0, pCut1, pCut ) )
return 0;
}
+ pCut->uSign = pCut0->uSign | pCut1->uSign;
return 1;
}
@@ -400,6 +407,7 @@ int If_CutCompareArea( If_Cut_t ** ppC0, If_Cut_t ** ppC1 )
***********************************************************************/
void If_ManSortCuts( If_Man_t * p, int Mode )
{
+/*
// sort the cuts
if ( Mode || p->pPars->fArea ) // area
qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareArea );
@@ -407,6 +415,115 @@ void If_ManSortCuts( If_Man_t * p, int Mode )
qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelayOld );
else
qsort( p->ppCuts, p->nCuts, sizeof(If_Cut_t *), (int (*)(const void *, const void *))If_CutCompareDelay );
+*/
+}
+
+/**Function*************************************************************
+
+ Synopsis [Comparison function for two cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int If_ManSortCompare( If_Man_t * p, If_Cut_t * pC0, If_Cut_t * pC1 )
+{
+ if ( p->SortMode == 1 ) // area
+ {
+ if ( pC0->Area < pC1->Area - 0.0001 )
+ return -1;
+ if ( pC0->Area > pC1->Area + 0.0001 )
+ return 1;
+ if ( pC0->AveRefs > pC1->AveRefs )
+ return -1;
+ if ( pC0->AveRefs < pC1->AveRefs )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ if ( pC0->Delay < pC1->Delay - 0.0001 )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + 0.0001 )
+ return 1;
+ return 0;
+ }
+ if ( p->SortMode == 0 ) // delay
+ {
+ if ( pC0->Delay < pC1->Delay - 0.0001 )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + 0.0001 )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ if ( pC0->Area < pC1->Area - 0.0001 )
+ return -1;
+ if ( pC0->Area > pC1->Area + 0.0001 )
+ return 1;
+ return 0;
+ }
+ assert( p->SortMode == 2 ); // delay old
+ if ( pC0->Delay < pC1->Delay - 0.0001 )
+ return -1;
+ if ( pC0->Delay > pC1->Delay + 0.0001 )
+ return 1;
+ if ( pC0->Area < pC1->Area - 0.0001 )
+ return -1;
+ if ( pC0->Area > pC1->Area + 0.0001 )
+ return 1;
+ if ( pC0->nLeaves < pC1->nLeaves )
+ return -1;
+ if ( pC0->nLeaves > pC1->nLeaves )
+ return 1;
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs incremental sorting of cuts.]
+
+ Description [Currently only the trivial sorting is implemented.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_CutSort( If_Man_t * p, If_Set_t * pCutSet, If_Cut_t * pCut )
+{
+// int Counter = 0;
+ int i;
+
+ // the new cut is the last one
+ assert( pCutSet->ppCuts[pCutSet->nCuts] == pCut );
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax );
+
+ // cut structure is empty
+ if ( pCutSet->nCuts == 0 )
+ {
+ pCutSet->nCuts++;
+ return;
+ }
+
+ // the cut will be added - find its place
+ for ( i = pCutSet->nCuts-1; i >= 0; i-- )
+ {
+// Counter++;
+ if ( If_ManSortCompare( p, pCutSet->ppCuts[i], pCut ) <= 0 )
+ break;
+ pCutSet->ppCuts[i+1] = pCutSet->ppCuts[i];
+ pCutSet->ppCuts[i] = pCut;
+ }
+// printf( "%d ", Counter );
+
+ // update the number of cuts
+ if ( pCutSet->nCuts < pCutSet->nCutsMax )
+ pCutSet->nCuts++;
}
/**Function*************************************************************
@@ -635,7 +752,7 @@ void If_CutLift( If_Cut_t * pCut )
SeeAlso []
***********************************************************************/
-void If_CutCopy( If_Cut_t * pCutDest, If_Cut_t * pCutSrc )
+void If_CutCopy( If_Man_t * p, If_Cut_t * pCutDest, If_Cut_t * pCutSrc )
{
int * pLeaves;
char * pPerm;
@@ -645,17 +762,11 @@ void If_CutCopy( If_Cut_t * pCutDest, If_Cut_t * pCutSrc )
pPerm = pCutDest->pPerm;
pTruth = pCutDest->pTruth;
// copy the cut info
- *pCutDest = *pCutSrc;
+ memcpy( pCutDest, pCutSrc, p->nCutBytes );
// restore the arrays
pCutDest->pLeaves = pLeaves;
pCutDest->pPerm = pPerm;
pCutDest->pTruth = pTruth;
- // copy the array data
- memcpy( pCutDest->pLeaves, pCutSrc->pLeaves, sizeof(int) * pCutSrc->nLeaves );
- if ( pCutSrc->pPerm )
- memcpy( pCutDest->pPerm, pCutSrc->pPerm, sizeof(unsigned) * If_CutPermWords(pCutSrc->nLimit) );
- if ( pCutSrc->pTruth )
- memcpy( pCutDest->pTruth, pCutSrc->pTruth, sizeof(unsigned) * If_CutTruthWords(pCutSrc->nLimit) );
}
////////////////////////////////////////////////////////////////////////
diff --git a/src/map/if/ifMan.c b/src/map/if/ifMan.c
index 84a0c52f..20b2657f 100644
--- a/src/map/if/ifMan.c
+++ b/src/map/if/ifMan.c
@@ -25,7 +25,9 @@
////////////////////////////////////////////////////////////////////////
static If_Obj_t * If_ManSetupObj( If_Man_t * p );
-static If_Cut_t ** If_ManSetupCuts( If_Man_t * p );
+
+static void If_ManCutSetRecycle( If_Man_t * p, If_Set_t * pSet ) { pSet->pNext = p->pFreeList; p->pFreeList = pSet; }
+static If_Set_t * If_ManCutSetFetch( If_Man_t * p ) { If_Set_t * pTemp = p->pFreeList; p->pFreeList = p->pFreeList->pNext; return pTemp; }
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
@@ -57,27 +59,26 @@ If_Man_t * If_ManStart( If_Par_t * pPars )
p->vMapped = Vec_PtrAlloc( 100 );
p->vTemp = Vec_PtrAlloc( 100 );
// prepare the memory manager
- p->nTruthSize = p->pPars->fTruth? If_CutTruthWords( p->pPars->nLutSize ) : 0;
- p->nPermSize = p->pPars->fUsePerm? If_CutPermWords( p->pPars->nLutSize ) : 0;
- p->nCutSize = sizeof(If_Cut_t) + sizeof(int) * (p->pPars->nLutSize + p->nPermSize + p->nTruthSize);
- p->nEntrySize = sizeof(If_Obj_t) + p->pPars->nCutsMax * p->nCutSize;
- p->nEntryBase = sizeof(If_Obj_t) + p->pPars->nCutsMax * sizeof(If_Cut_t);
- p->pMem = Mem_FixedStart( p->nEntrySize );
+ p->nTruthWords = p->pPars->fTruth? If_CutTruthWords( p->pPars->nLutSize ) : 0;
+ p->nPermWords = p->pPars->fUsePerm? If_CutPermWords( p->pPars->nLutSize ) : 0;
+ p->nObjBytes = sizeof(If_Obj_t) + sizeof(int) * (p->pPars->nLutSize + p->nPermWords + p->nTruthWords);
+ p->nCutBytes = sizeof(If_Cut_t) + sizeof(int) * (p->pPars->nLutSize + p->nPermWords + p->nTruthWords);
+ p->nSetBytes = sizeof(If_Set_t) + (sizeof(If_Cut_t *) + p->nCutBytes) * (p->pPars->nCutsMax + 1);
+ p->pMemObj = Mem_FixedStart( p->nObjBytes );
+// p->pMemSet = Mem_FixedStart( p->nSetBytes );
// report expected memory usage
if ( p->pPars->fVerbose )
- printf( "Memory (bytes): Truth = %3d. Cut = %3d. Entry = %4d. Total = %.2f Mb / 1K AIG nodes\n",
- 4 * p->nTruthSize, p->nCutSize, p->nEntrySize, 1000.0 * p->nEntrySize / (1<<20) );
+ printf( "Memory (bytes): Truth = %4d. Cut = %4d. Obj = %4d. Set = %4d.\n",
+ 4 * p->nTruthWords, p->nCutBytes, p->nObjBytes, p->nSetBytes );
// room for temporary truth tables
- p->puTemp[0] = p->pPars->fTruth? ALLOC( unsigned, 4 * p->nTruthSize ) : NULL;
- p->puTemp[1] = p->puTemp[0] + p->nTruthSize;
- p->puTemp[2] = p->puTemp[1] + p->nTruthSize;
- p->puTemp[3] = p->puTemp[2] + p->nTruthSize;
+ p->puTemp[0] = p->pPars->fTruth? ALLOC( unsigned, 4 * p->nTruthWords ) : NULL;
+ p->puTemp[1] = p->puTemp[0] + p->nTruthWords;
+ p->puTemp[2] = p->puTemp[1] + p->nTruthWords;
+ p->puTemp[3] = p->puTemp[2] + p->nTruthWords;
// create the constant node
p->pConst1 = If_ManSetupObj( p );
p->pConst1->Type = IF_CONST1;
p->pConst1->fPhase = 1;
- // create temporary cuts
- p->ppCuts = If_ManSetupCuts( p );
return p;
}
@@ -94,8 +95,6 @@ If_Man_t * If_ManStart( If_Par_t * pPars )
***********************************************************************/
void If_ManStop( If_Man_t * p )
{
- If_Cut_t * pTemp;
- int i;
Vec_PtrFree( p->vCis );
Vec_PtrFree( p->vCos );
Vec_PtrFree( p->vObjs );
@@ -103,20 +102,16 @@ void If_ManStop( If_Man_t * p )
Vec_PtrFree( p->vTemp );
if ( p->vLatchOrder ) Vec_PtrFree( p->vLatchOrder );
if ( p->vLags ) Vec_IntFree( p->vLags );
- Mem_FixedStop( p->pMem, 0 );
+ Mem_FixedStop( p->pMemObj, 0 );
+// Mem_FixedStop( p->pMemSet, 0 );
+ FREE( p->pMemCi );
+ FREE( p->pMemAnd );
+ FREE( p->puTemp[0] );
// free pars memory
if ( p->pPars->pTimesArr )
FREE( p->pPars->pTimesArr );
if ( p->pPars->pTimesReq )
FREE( p->pPars->pTimesReq );
- // free temporary cut memory
- pTemp = p->ppCuts[0];
- for ( i = 1; i < 1 + p->pPars->nCutsMax * p->pPars->nCutsMax; i++ )
- if ( pTemp > p->ppCuts[i] )
- pTemp = p->ppCuts[i];
- FREE( p->puTemp[0] );
- free( pTemp );
- free( p->ppCuts );
free( p );
}
@@ -159,7 +154,7 @@ If_Obj_t * If_ManCreateCo( If_Man_t * p, If_Obj_t * pDriver, int fCompl0 )
pObj->Type = IF_CO;
pObj->fCompl0 = fCompl0;
Vec_PtrPush( p->vCos, pObj );
- pObj->pFanin0 = pDriver; pDriver->nRefs++;
+ pObj->pFanin0 = pDriver; pDriver->nRefs++;
p->nObjs[IF_CO]++;
return pObj;
}
@@ -183,8 +178,8 @@ If_Obj_t * If_ManCreateAnd( If_Man_t * p, If_Obj_t * pFan0, int fCompl0, If_Obj_
pObj->Type = IF_AND;
pObj->fCompl0 = fCompl0;
pObj->fCompl1 = fCompl1;
- pObj->pFanin0 = pFan0; pFan0->nRefs++;
- pObj->pFanin1 = pFan1; pFan1->nRefs++;
+ pObj->pFanin0 = pFan0; pFan0->nRefs++; pFan0->nVisits++; pFan0->nVisitsCopy++;
+ pObj->pFanin1 = pFan1; pFan1->nRefs++; pFan1->nVisits++; pFan1->nVisitsCopy++;
pObj->fPhase = (fCompl0 ^ pFan0->fPhase) & (fCompl1 ^ pFan1->fPhase);
pObj->Level = 1 + IF_MAX( pFan0->Level, pFan1->Level );
if ( p->nLevelMax < (int)pObj->Level )
@@ -211,8 +206,11 @@ void If_ManCreateChoice( If_Man_t * p, If_Obj_t * pObj )
assert( pObj->fRepr == 0 );
pObj->fRepr = 1;
// update the level of this node (needed for correct required time computation)
- for ( pTemp = pObj->pEquiv; pTemp; pTemp = pTemp->pEquiv )
+ for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv )
+ {
pObj->Level = IF_MAX( pObj->Level, pTemp->Level );
+ pTemp->nVisits++; pTemp->nVisitsCopy++;
+ }
// mark the largest level
if ( p->nLevelMax < (int)pObj->Level )
p->nLevelMax = (int)pObj->Level;
@@ -220,7 +218,7 @@ void If_ManCreateChoice( If_Man_t * p, If_Obj_t * pObj )
/**Function*************************************************************
- Synopsis [Prepares memory for the node with cuts.]
+ Synopsis [Prepares memory for one cut.]
Description []
@@ -229,49 +227,102 @@ void If_ManCreateChoice( If_Man_t * p, If_Obj_t * pObj )
SeeAlso []
***********************************************************************/
-If_Obj_t * If_ManSetupObj( If_Man_t * p )
+void If_ManSetupCut( If_Man_t * p, If_Cut_t * pCut )
{
- If_Cut_t * pCut;
- If_Obj_t * pObj;
- int i, * pArrays, nTruthWords;
- // get memory for the object
- pObj = (If_Obj_t *)Mem_FixedEntryFetch( p->pMem );
- memset( pObj, 0, p->nEntryBase );
- // organize memory
- pArrays = (int *)((char *)pObj + p->nEntryBase);
- for ( i = 0; i < p->pPars->nCutsMax; i++ )
+ memset( pCut, 0, sizeof(If_Cut_t) );
+ pCut->nLimit = p->pPars->nLutSize;
+ pCut->pLeaves = (int *)(pCut + 1);
+ if ( p->pPars->fUsePerm )
+ pCut->pPerm = (char *)(pCut->pLeaves + p->pPars->nLutSize);
+ if ( p->pPars->fTruth )
+ pCut->pTruth = pCut->pLeaves + p->pPars->nLutSize + p->nPermWords;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares memory for one cutset.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSetupSet( If_Man_t * p, If_Set_t * pSet )
+{
+ char * pArray;
+ int i;
+ pSet->nCuts = 0;
+ pSet->nCutsMax = p->pPars->nCutsMax;
+ pSet->ppCuts = (If_Cut_t **)(pSet + 1);
+ pArray = (char *)pSet->ppCuts + sizeof(If_Cut_t *) * (pSet->nCutsMax+1);
+ for ( i = 0; i <= pSet->nCutsMax; i++ )
{
- pCut = pObj->Cuts + i;
- pCut->nLimit = p->pPars->nLutSize;
- pCut->pLeaves = pArrays + i * p->pPars->nLutSize;
- pCut->pPerm = (char *)(p->pPars->fUsePerm? pArrays + p->pPars->nCutsMax * p->pPars->nLutSize + i * p->nPermSize : NULL);
- pCut->pTruth = p->pPars->fTruth? pArrays + p->pPars->nCutsMax * (p->pPars->nLutSize + p->nPermSize) + i * p->nTruthSize : NULL;
+ pSet->ppCuts[i] = (If_Cut_t *)(pArray + i * p->nCutBytes);
+ If_ManSetupCut( p, pSet->ppCuts[i] );
}
- // assign ID and save
- pObj->Id = Vec_PtrSize(p->vObjs);
- Vec_PtrPush( p->vObjs, pObj );
- // assign elementary cut
- pCut = pObj->Cuts;
+// pArray += (pSet->nCutsMax + 1) * p->nCutBytes;
+// assert( ((char *)pArray) - ((char *)pSet) == p->nSetBytes );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares memory for one cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSetupCutTriv( If_Man_t * p, If_Cut_t * pCut, int ObjId )
+{
+ pCut->fCompl = 0;
+ pCut->nLimit = p->pPars->nLutSize;
pCut->nLeaves = 1;
- pCut->pLeaves[0] = p->pPars->fLiftLeaves? (pObj->Id << 8) : pObj->Id;
+ pCut->pLeaves[0] = p->pPars->fLiftLeaves? (ObjId << 8) : ObjId;
pCut->uSign = If_ObjCutSign( pCut->pLeaves[0] );
- // set the number of cuts
- pObj->nCuts = 1;
- // set the required times
- pObj->Required = IF_FLOAT_LARGE;
// set up elementary truth table of the unit cut
if ( p->pPars->fTruth )
{
+ int i, nTruthWords;
nTruthWords = Extra_TruthWordNum( pCut->nLimit );
for ( i = 0; i < nTruthWords; i++ )
If_CutTruth(pCut)[i] = 0xAAAAAAAA;
}
+}
+
+/**Function*************************************************************
+
+ Synopsis [Prepares memory for the node with cuts.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Obj_t * If_ManSetupObj( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ // get memory for the object
+ pObj = (If_Obj_t *)Mem_FixedEntryFetch( p->pMemObj );
+ memset( pObj, 0, sizeof(If_Obj_t) );
+ If_ManSetupCut( p, &pObj->CutBest );
+ // assign ID and save
+ pObj->Id = Vec_PtrSize(p->vObjs);
+ Vec_PtrPush( p->vObjs, pObj );
+ // set the required times
+ pObj->Required = IF_FLOAT_LARGE;
return pObj;
}
/**Function*************************************************************
- Synopsis [Prepares memory for additional cuts of the manager.]
+ Synopsis [Prepares memory for one cut.]
Description []
@@ -280,31 +331,162 @@ If_Obj_t * If_ManSetupObj( If_Man_t * p )
SeeAlso []
***********************************************************************/
-If_Cut_t ** If_ManSetupCuts( If_Man_t * p )
+void If_ManSetupCiCutSets( If_Man_t * p )
{
- If_Cut_t ** pCutStore;
- int * pArrays, nCutsTotal, i;
- // decide how many cuts to alloc
- nCutsTotal = 1 + p->pPars->nCutsMax * p->pPars->nCutsMax;
- // allocate and clean space for cuts
- pCutStore = (If_Cut_t **)ALLOC( If_Cut_t *, (nCutsTotal + 1) );
- memset( pCutStore, 0, sizeof(If_Cut_t *) * (nCutsTotal + 1) );
- pCutStore[0] = (If_Cut_t *)ALLOC( char, p->nCutSize * nCutsTotal );
- memset( pCutStore[0], 0, p->nCutSize * nCutsTotal );
- // assign cut paramters and space for the cut leaves
- assert( sizeof(int) == sizeof(unsigned) );
- pArrays = (int *)((char *)pCutStore[0] + sizeof(If_Cut_t) * nCutsTotal);
- for ( i = 0; i < nCutsTotal; i++ )
+ If_Obj_t * pObj;
+ int i;
+ assert( p->pMemCi == NULL );
+ // create elementary cuts for the CIs
+ If_ManForEachCi( p, pObj, i )
+ If_ManSetupCutTriv( p, &pObj->CutBest, pObj->Id );
+ // create elementary cutsets for the CIs
+ p->pMemCi = (If_Set_t *)malloc( If_ManCiNum(p) * (sizeof(If_Set_t) + sizeof(void *)) );
+ If_ManForEachCi( p, pObj, i )
{
- pCutStore[i] = (If_Cut_t *)((char *)pCutStore[0] + sizeof(If_Cut_t) * i);
- pCutStore[i]->nLimit = p->pPars->nLutSize;
- pCutStore[i]->pLeaves = pArrays + i * p->pPars->nLutSize;
- pCutStore[i]->pPerm = (char *)(p->pPars->fUsePerm? pArrays + nCutsTotal * p->pPars->nLutSize + i * p->nPermSize : NULL);
- pCutStore[i]->pTruth = p->pPars->fTruth? pArrays + nCutsTotal * (p->pPars->nLutSize + p->nPermSize) + i * p->nTruthSize : NULL;
+ pObj->pCutSet = (If_Set_t *)((char *)p->pMemCi + i * (sizeof(If_Set_t) + sizeof(void *)));
+ pObj->pCutSet->nCuts = 1;
+ pObj->pCutSet->nCutsMax = p->pPars->nCutsMax;
+ pObj->pCutSet->ppCuts = (If_Cut_t **)(pObj->pCutSet + 1);
+ pObj->pCutSet->ppCuts[0] = &pObj->CutBest;
}
- return pCutStore;
}
+/**Function*************************************************************
+
+ Synopsis [Prepares cutset of the node.]
+
+ Description [Elementary cutset will be added last.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+If_Set_t * If_ManSetupNodeCutSet( If_Man_t * p, If_Obj_t * pObj )
+{
+ assert( If_ObjIsAnd(pObj) );
+ assert( pObj->pCutSet == NULL );
+// pObj->pCutSet = (If_Set_t *)Mem_FixedEntryFetch( p->pMemSet );
+// If_ManSetupSet( p, pObj->pCutSet );
+
+ pObj->pCutSet = If_ManCutSetFetch( p );
+ pObj->pCutSet->nCuts = 0;
+ pObj->pCutSet->nCutsMax = p->pPars->nCutsMax;
+
+ return pObj->pCutSet;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Dereferences cutset of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManDerefNodeCutSet( If_Man_t * p, If_Obj_t * pObj )
+{
+ If_Obj_t * pFanin;
+ assert( If_ObjIsAnd(pObj) );
+ // consider the node
+ assert( pObj->nVisits >= 0 );
+ if ( pObj->nVisits == 0 )
+ {
+// Mem_FixedEntryRecycle( p->pMemSet, (char *)pObj->pCutSet );
+ If_ManCutSetRecycle( p, pObj->pCutSet );
+ pObj->pCutSet = NULL;
+ }
+ // consider the first fanin
+ pFanin = If_ObjFanin0(pObj);
+ assert( pFanin->nVisits > 0 );
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ {
+// Mem_FixedEntryRecycle( p->pMemSet, (char *)pFanin->pCutSet );
+ If_ManCutSetRecycle( p, pFanin->pCutSet );
+ pFanin->pCutSet = NULL;
+ }
+ // consider the second fanin
+ pFanin = If_ObjFanin1(pObj);
+ assert( pFanin->nVisits > 0 );
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ {
+// Mem_FixedEntryRecycle( p->pMemSet, (char *)pFanin->pCutSet );
+ If_ManCutSetRecycle( p, pFanin->pCutSet );
+ pFanin->pCutSet = NULL;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Dereferences cutset of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManDerefChoiceCutSet( If_Man_t * p, If_Obj_t * pObj )
+{
+ If_Obj_t * pTemp;
+ assert( If_ObjIsAnd(pObj) );
+ assert( pObj->fRepr );
+ assert( pObj->nVisits > 0 );
+ // consider the nodes in the choice class
+ for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv )
+ {
+ assert( pTemp == pObj || pTemp->nVisits == 1 );
+ if ( --pTemp->nVisits == 0 )
+ {
+// Mem_FixedEntryRecycle( p->pMemSet, (char *)pTemp->pCutSet );
+ If_ManCutSetRecycle( p, pTemp->pCutSet );
+ pTemp->pCutSet = NULL;
+ }
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Dereferences cutset of the node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void If_ManSetupSetAll( If_Man_t * p )
+{
+ If_Set_t * pCutSet;
+ int i, nCrossCut, nCutSets;
+ nCrossCut = If_ManCrossCut( p );
+ nCutSets = 128 + nCrossCut;
+ p->pFreeList = p->pMemAnd = pCutSet = (If_Set_t *)malloc( nCutSets * p->nSetBytes );
+ for ( i = 0; i < nCutSets; i++ )
+ {
+ If_ManSetupSet( p, pCutSet );
+ if ( i == nCutSets - 1 )
+ pCutSet->pNext = NULL;
+ else
+ pCutSet->pNext = (If_Set_t *)( (char *)pCutSet + p->nSetBytes );
+ pCutSet = pCutSet->pNext;
+ }
+ assert( pCutSet == NULL );
+
+ if ( p->pPars->fVerbose )
+ {
+ printf( "Total memory = %7.2f Mb. Peak cut memory = %7.2f Mb. \n",
+ 1.0 * (p->nObjBytes + 2*sizeof(void *)) * If_ManObjNum(p) / (1<<20),
+ 1.0 * p->nSetBytes * nCrossCut / (1<<20) );
+ }
+// printf( "Cross cut = %d.\n", nCrossCut );
+
+}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
diff --git a/src/map/if/ifMap.c b/src/map/if/ifMap.c
index 2d04d780..90d7b4e8 100644
--- a/src/map/if/ifMap.c
+++ b/src/map/if/ifMap.c
@@ -24,16 +24,6 @@
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
-/*
- Ideas to try:
- - reverse order of area recovery
- - ordering of the outputs by size
- - merging Delay, Delay2, and Area
- - expand/reduce area recovery
- - use average nrefs for tie-breaking
-
-*/
-
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
@@ -69,13 +59,14 @@ static inline int If_WordCountOnes( unsigned uWord )
SeeAlso []
***********************************************************************/
-void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode )
+void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess )
{
+ If_Set_t * pCutSet;
If_Cut_t * pCut0, * pCut1, * pCut;
- int i, k, iCut;
+ int i, k;
- assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->nCuts > 1 );
- assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->nCuts > 1 );
+ assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin0) || pObj->pFanin0->pCutSet->nCuts > 1 );
+ assert( p->pPars->fSeqMap || !If_ObjIsAnd(pObj->pFanin1) || pObj->pFanin1->pCutSet->nCuts > 1 );
// prepare
if ( !p->pPars->fSeqMap )
@@ -88,40 +79,41 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode )
if ( Mode && pObj->nRefs > 0 )
If_CutDeref( p, If_ObjCutBest(pObj), IF_INFINITY );
- // save the best cut as one of the candidate cuts
- p->nCuts = 0;
- p->nCutsMerged++;
- if ( Mode )
+ // prepare the cutset
+ pCutSet = If_ManSetupNodeCutSet( p, pObj );
+
+ // get the current assigned best cut
+ pCut = If_ObjCutBest(pObj);
+ if ( pCut->nLeaves > 0 )
{
// recompute the parameters of the best cut
- pCut = If_ObjCutBest(pObj);
pCut->Delay = If_CutDelay( p, pCut );
assert( pCut->Delay <= pObj->Required + p->fEpsilon );
- pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut );
+ pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut );
// save the best cut from the previous iteration
- If_CutCopy( p->ppCuts[p->nCuts++], pCut );
- p->nCutsMerged++;
+ if ( !fPreprocess )
+ If_CutCopy( p, pCutSet->ppCuts[pCutSet->nCuts++], pCut );
}
- // prepare room for the next cut
- iCut = p->nCuts;
- pCut = p->ppCuts[iCut];
// generate cuts
If_ObjForEachCut( pObj->pFanin0, pCut0, i )
If_ObjForEachCut( pObj->pFanin1, pCut1, k )
{
+ // get the next free cut
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax );
+ pCut = pCutSet->ppCuts[pCutSet->nCuts];
// make sure K-feasible cut exists
if ( If_WordCountOnes(pCut0->uSign | pCut1->uSign) > p->pPars->nLutSize )
continue;
// merge the nodes
if ( !If_CutMerge( pCut0, pCut1, pCut ) )
continue;
+ assert( p->pPars->fSeqMap || pCut->nLeaves > 1 );
+ p->nCutsMerged++;
// check if this cut is contained in any of the available cuts
- pCut->uSign = pCut0->uSign | pCut1->uSign;
// if ( p->pPars->pFuncCost == NULL && If_CutFilter( p, pCut ) ) // do not filter functionality cuts
- if ( If_CutFilter( p, pCut ) )
+ if ( If_CutFilter( pCutSet, pCut ) )
continue;
- // the cuts have been successfully merged
// compute the truth table
pCut->fCompl = 0;
if ( p->pPars->fTruth )
@@ -129,6 +121,8 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode )
// compute the application-specific cost and depth
pCut->fUser = (p->pPars->pFuncCost != NULL);
pCut->Cost = p->pPars->pFuncCost? p->pPars->pFuncCost(pCut) : 0;
+ if ( pCut->Cost == IF_COST_MAX )
+ continue;
// check if the cut satisfies the required times
pCut->Delay = If_CutDelay( p, pCut );
// printf( "%.2f ", pCut->Delay );
@@ -137,30 +131,26 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode )
// compute area of the cut (this area may depend on the application specific cost)
pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut );
pCut->AveRefs = (Mode == 0)? (float)0.0 : If_CutAverageRefs( p, pCut );
- // make sure the cut is the last one (after filtering it may not be so)
- assert( pCut == p->ppCuts[iCut] );
- p->ppCuts[iCut] = p->ppCuts[p->nCuts];
- p->ppCuts[p->nCuts] = pCut;
- // count the cut
- p->nCuts++;
- p->nCutsMerged++;
- // prepare room for the next cut
- iCut = p->nCuts;
- pCut = p->ppCuts[iCut];
+ // insert the cut into storage
+ If_CutSort( p, pCutSet, pCut );
}
- assert( p->nCuts > 0 );
- // sort if we have more cuts
- 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( pCutSet->nCuts > 0 );
+
+ // add the trivial cut to the set
+ If_ManSetupCutTriv( p, pCutSet->ppCuts[pCutSet->nCuts++], pObj->Id );
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax+1 );
+
+ // update the best cut
+ if ( !fPreprocess || pCutSet->ppCuts[0]->Delay <= pObj->Required + p->fEpsilon )
+ If_CutCopy( p, If_ObjCutBest(pObj), pCutSet->ppCuts[0] );
assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 );
+
// ref the selected cut
if ( Mode && pObj->nRefs > 0 )
If_CutRef( p, If_ObjCutBest(pObj), IF_INFINITY );
+
+ // free the cuts
+ If_ManDerefNodeCutSet( p, pObj );
}
/**Function*************************************************************
@@ -174,70 +164,73 @@ void If_ObjPerformMappingAnd( If_Man_t * p, If_Obj_t * pObj, int Mode )
SeeAlso []
***********************************************************************/
-void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode )
+void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode, int fPreprocess )
{
+ If_Set_t * pCutSet;
If_Obj_t * pTemp;
If_Cut_t * pCutTemp, * pCut;
- int i, iCut;
+ int i;
assert( pObj->pEquiv != NULL );
+
// prepare
if ( Mode && pObj->nRefs > 0 )
If_CutDeref( p, If_ObjCutBest(pObj), IF_INFINITY );
- // prepare room for the next cut
- p->nCuts = 0;
- iCut = p->nCuts;
- pCut = p->ppCuts[iCut];
- // generate cuts
+
+ // remove elementary cuts
for ( pTemp = pObj; pTemp; pTemp = pTemp->pEquiv )
+ pTemp->pCutSet->nCuts--;
+
+ // update the cutset of the node
+ pCutSet = pObj->pCutSet;
+
+ // generate cuts
+ for ( pTemp = pObj->pEquiv; pTemp; pTemp = pTemp->pEquiv )
{
- If_ObjForEachCutStart( pTemp, pCutTemp, i, 1 )
+ assert( pTemp->nRefs == 0 );
+ assert( p->pPars->fSeqMap || pTemp->pCutSet->nCuts > 0 );
+ // go through the cuts of this node
+ If_ObjForEachCut( pTemp, pCutTemp, i )
{
- assert( pTemp->nCuts > 1 );
- assert( pTemp == pObj || pTemp->nRefs == 0 );
+ assert( p->pPars->fSeqMap || pCutTemp->nLeaves > 1 );
+ // get the next free cut
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax );
+ pCut = pCutSet->ppCuts[pCutSet->nCuts];
// copy the cut into storage
- If_CutCopy( pCut, pCutTemp );
+ If_CutCopy( p, pCut, pCutTemp );
// check if this cut is contained in any of the available cuts
- if ( If_CutFilter( p, pCut ) )
+ if ( If_CutFilter( pCutSet, pCut ) )
continue;
- // the cuts have been successfully merged
// check if the cut satisfies the required times
assert( pCut->Delay == If_CutDelay( p, pCut ) );
if ( Mode && pCut->Delay > pObj->Required + p->fEpsilon )
continue;
// set the phase attribute
- pCut->fCompl ^= (pObj->fPhase ^ pTemp->fPhase);
+ assert( pCut->fCompl == 0 );
+ pCut->fCompl ^= (pObj->fPhase ^ pTemp->fPhase); // why ^= ?
// compute area of the cut (this area may depend on the application specific cost)
pCut->Area = (Mode == 2)? If_CutAreaDerefed( p, pCut, IF_INFINITY ) : If_CutFlow( p, pCut );
pCut->AveRefs = (Mode == 0)? (float)0.0 : If_CutAverageRefs( p, pCut );
- // make sure the cut is the last one (after filtering it may not be so)
- assert( pCut == p->ppCuts[iCut] );
- p->ppCuts[iCut] = p->ppCuts[p->nCuts];
- p->ppCuts[p->nCuts] = pCut;
- // count the cut
- p->nCuts++;
- // prepare room for the next cut
- iCut = p->nCuts;
- pCut = p->ppCuts[iCut];
- // quit if we exceeded the number of cuts
- if ( p->nCuts >= p->pPars->nCutsMax * p->pPars->nCutsMax )
- break;
+ // insert the cut into storage
+ If_CutSort( p, pCutSet, pCut );
}
- // quit if we exceeded the number of cuts
- if ( p->nCuts >= p->pPars->nCutsMax * p->pPars->nCutsMax )
- break;
}
- assert( p->nCuts > 0 );
- // sort if we have more cuts
- If_ManSortCuts( p, Mode );
- // decide how many cuts to use
- pObj->nCuts = IF_MIN( p->nCuts + 1, p->nCutsUsed );
- // take the first
- If_ObjForEachCutStart( pObj, pCut, i, 1 )
- If_CutCopy( pCut, p->ppCuts[i-1] );
+ assert( pCutSet->nCuts > 0 );
+
+ // add the trivial cut to the set
+ If_ManSetupCutTriv( p, pCutSet->ppCuts[pCutSet->nCuts++], pObj->Id );
+ assert( pCutSet->nCuts <= pCutSet->nCutsMax+1 );
+
+ // update the best cut
+ if ( !fPreprocess || pCutSet->ppCuts[0]->Delay <= pObj->Required + p->fEpsilon )
+ If_CutCopy( p, If_ObjCutBest(pObj), pCutSet->ppCuts[0] );
assert( p->pPars->fSeqMap || If_ObjCutBest(pObj)->nLeaves > 1 );
+
// ref the selected cut
if ( Mode && pObj->nRefs > 0 )
If_CutRef( p, If_ObjCutBest(pObj), IF_INFINITY );
+
+ // free the cuts
+ If_ManDerefChoiceCutSet( p, pObj );
}
/**Function*************************************************************
@@ -251,12 +244,19 @@ void If_ObjPerformMappingChoice( If_Man_t * p, If_Obj_t * pObj, int Mode )
SeeAlso []
***********************************************************************/
-int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fRequired, char * pLabel )
+int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fPreprocess, char * pLabel )
{
// ProgressBar * pProgress;
If_Obj_t * pObj;
int i, clk = clock();
assert( Mode >= 0 && Mode <= 2 );
+ // set the sorting function
+ if ( Mode || p->pPars->fArea ) // area
+ p->SortMode = 1;
+ else if ( p->pPars->fFancy )
+ p->SortMode = 2;
+ else
+ p->SortMode = 0;
// set the cut number
p->nCutsUsed = nCutsUsed;
p->nCutsMerged = 0;
@@ -265,24 +265,24 @@ int If_ManPerformMappingRound( If_Man_t * p, int nCutsUsed, int Mode, int fRequi
If_ManForEachNode( p, pObj, i )
{
// Extra_ProgressBarUpdate( pProgress, i, pLabel );
- If_ObjPerformMappingAnd( p, pObj, Mode );
+ If_ObjPerformMappingAnd( p, pObj, Mode, fPreprocess );
if ( pObj->fRepr )
- If_ObjPerformMappingChoice( p, pObj, Mode );
+ If_ObjPerformMappingChoice( p, pObj, Mode, fPreprocess );
}
// Extra_ProgressBarStop( pProgress );
+ // make sure the visit counters are all zero
+ If_ManForEachNode( p, pObj, i )
+ assert( pObj->nVisits == 0 );
// compute required times and stats
- if ( fRequired )
+ If_ManComputeRequired( p );
+ if ( p->pPars->fVerbose )
{
- If_ManComputeRequired( p, Mode==0 );
- if ( p->pPars->fVerbose )
- {
- char Symb = (Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A');
- printf( "%c: Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ",
- Symb, p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
- PRT( "T", clock() - clk );
+ char Symb = fPreprocess? 'P' : ((Mode == 0)? 'D' : ((Mode == 1)? 'F' : 'A'));
+ printf( "%c: Del = %6.2f. Ar = %8.2f. Net = %6d. Cut = %8d. ",
+ Symb, p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged );
+ PRT( "T", clock() - clk );
// printf( "Max number of cuts = %d. Average number of cuts = %5.2f.\n",
// p->nCutsMax, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
- }
}
return 1;
}
diff --git a/src/map/if/ifPrepro.c b/src/map/if/ifPrepro.c
deleted file mode 100644
index 32146e91..00000000
--- a/src/map/if/ifPrepro.c
+++ /dev/null
@@ -1,175 +0,0 @@
-/**CFile****************************************************************
-
- FileName [ifPrepro.c]
-
- SystemName [ABC: Logic synthesis and verification system.]
-
- PackageName [FPGA mapping based on priority cuts.]
-
- Synopsis [Selects the starting mapping.]
-
- Author [Alan Mishchenko]
-
- Affiliation [UC Berkeley]
-
- Date [Ver. 1.0. Started - November 21, 2006.]
-
- Revision [$Id: ifPrepro.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
-
-***********************************************************************/
-
-#include "if.h"
-
-////////////////////////////////////////////////////////////////////////
-/// DECLARATIONS ///
-////////////////////////////////////////////////////////////////////////
-
-static void If_ManPerformMappingMoveBestCut( If_Man_t * p, int iPosNew, int iPosOld );
-static void If_ManPerformMappingAdjust( If_Man_t * p, int nCuts );
-
-////////////////////////////////////////////////////////////////////////
-/// FUNCTION DEFINITIONS ///
-////////////////////////////////////////////////////////////////////////
-
-/**Function*************************************************************
-
- Synopsis [Merges the results of delay, relaxed delay and area-based mapping.]
-
- Description [Delay target may be different from minimum delay!!!]
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void If_ManPerformMappingPreprocess( If_Man_t * p )
-{
- float delayArea, delayDelay, delayPure;
- int clk = clock();
- assert( p->pPars->nCutsMax >= 4 );
-
- // perform min-area mapping and move the cut to the end
- p->pPars->fArea = 1;
- If_ManPerformMappingRound( p, p->pPars->nCutsMax, 0, 0, "Start delay" );
- p->pPars->fArea = 0;
- 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 );
-
- // perfrom min-delay mapping and move the cut to the end
- p->pPars->fFancy = 1;
- If_ManPerformMappingRound( p, p->pPars->nCutsMax - 1, 0, 0, "Start delay-2" );
- p->pPars->fFancy = 0;
- 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, 0 );
- if ( p->pPars->DelayTarget != -1 && delayPure < p->pPars->DelayTarget - p->fEpsilon )
- delayPure = p->pPars->DelayTarget;
-
- // decide what to do
- if ( delayPure < delayDelay - p->fEpsilon && delayPure < delayArea - p->fEpsilon )
- {
- // copy the remaining two cuts
- if ( p->pPars->nCutsMax > 4 )
- {
- If_ManPerformMappingMoveBestCut( p, 2, p->pPars->nCutsMax - 2 );
- If_ManPerformMappingMoveBestCut( p, 3, p->pPars->nCutsMax - 1 );
- }
- If_ManComputeRequired( p, 1 );
- If_ManPerformMappingAdjust( p, 4 );
- }
- else if ( delayDelay < delayArea - p->fEpsilon )
- {
- If_ManPerformMappingMoveBestCut( p, 1, p->pPars->nCutsMax - 2 );
- If_ManPerformMappingMoveBestCut( p, 2, p->pPars->nCutsMax - 1 );
- If_ManComputeRequired( p, 1 );
- If_ManPerformMappingAdjust( p, 3 );
- }
- else
- {
- If_ManPerformMappingMoveBestCut( p, 1, p->pPars->nCutsMax - 1 );
- If_ManComputeRequired( p, 1 );
- If_ManPerformMappingAdjust( p, 2 );
- }
- If_ManComputeRequired( p, 1 );
- if ( p->pPars->fVerbose )
- {
- printf( "S: Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ",
- p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
- PRT( "T", clock() - clk );
- }
-}
-
-/**Function*************************************************************
-
- Synopsis [Moves the best cut to the given position.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void If_ManPerformMappingMoveBestCut( If_Man_t * p, int iPosNew, int iPosOld )
-{
- If_Obj_t * pObj;
- int i;
- assert( iPosOld != iPosNew );
- assert( iPosOld > 0 && iPosOld < p->pPars->nCutsMax );
- assert( iPosNew > 0 && iPosNew < p->pPars->nCutsMax );
- If_ManForEachNode( p, pObj, i )
- If_CutCopy( pObj->Cuts + iPosNew, pObj->Cuts + iPosOld );
-}
-
-/**Function*************************************************************
-
- Synopsis [Adjusts mapping for the given cuts.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void If_ManPerformMappingAdjust( If_Man_t * p, int nCuts )
-{
- If_Cut_t * pCut, * pCutBest;
- If_Obj_t * pObj;
- int i, c;
- assert( nCuts >= 2 && nCuts <= 4 );
- If_ManForEachNode( p, pObj, i )
- {
- pCutBest = NULL;
- for ( c = 1; c < nCuts; c++ )
- {
- pCut = pObj->Cuts + c;
- pCut->Delay = If_CutDelay( p, pCut );
- pCut->Area = If_CutFlow( p, pCut );
- assert( pCutBest || pCut->Delay < pObj->Required + p->fEpsilon );
- if ( pCutBest == NULL ||
- (pCut->Delay < pObj->Required + p->fEpsilon &&
- pCut->Area < pCutBest->Area - p->fEpsilon) )
- pCutBest = pCut;
- }
- assert( pCutBest != NULL );
- // check if we need to move
- if ( pCutBest != pObj->Cuts + 1 )
- If_CutCopy( pObj->Cuts + 1, pCutBest );
- // set the number of cuts
- pObj->nCuts = 2;
- }
-}
-
-////////////////////////////////////////////////////////////////////////
-/// END OF FILE ///
-////////////////////////////////////////////////////////////////////////
-
-
diff --git a/src/map/if/ifReduce.c b/src/map/if/ifReduce.c
index 26989b8c..1b23b883 100644
--- a/src/map/if/ifReduce.c
+++ b/src/map/if/ifReduce.c
@@ -52,11 +52,11 @@ void If_ManImproveMapping( If_Man_t * p )
clk = clock();
If_ManImproveExpand( p, p->pPars->nLutSize );
- If_ManComputeRequired( p, 0 );
+ If_ManComputeRequired( p );
if ( p->pPars->fVerbose )
{
- printf( "E: Del = %6.2f. Area = %8.2f. Nets = %6d. Cuts = %8d. Lim = %2d. Ave = %5.2f. ",
- p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged, p->nCutsUsed, 1.0 * p->nCutsMerged / If_ManAndNum(p) );
+ printf( "E: Del = %6.2f. Ar = %8.2f. Net = %6d. Cut = %8d. ",
+ p->RequiredGlo, p->AreaGlo, p->nNets, p->nCutsMerged );
PRT( "T", clock() - clk );
}
@@ -488,6 +488,7 @@ void If_ManImproveNodeFaninCompact( If_Man_t * p, If_Obj_t * pObj, int nLimit, V
***********************************************************************/
void If_ManImproveNodeReduce( If_Man_t * p, If_Obj_t * pObj, int nLimit )
{
+/*
If_Cut_t * pCut, * pCut0, * pCut1, * pCutR;
If_Obj_t * pFanin0, * pFanin1;
float AreaBef, AreaAft;
@@ -537,13 +538,14 @@ void If_ManImproveNodeReduce( If_Man_t * p, If_Obj_t * pObj, int nLimit )
AreaAft = If_CutAreaDerefed( p, pCutR, IF_INFINITY );
// update the best cut
if ( AreaAft < AreaBef - p->fEpsilon && pCutR->Delay < pObj->Required + p->fEpsilon )
- If_CutCopy( pCut, pCutR );
+ If_CutCopy( p, pCut, pCutR );
}
// recompute the delay of the best cut
pCut->Delay = If_CutDelay( p, pCut );
// ref the cut if the node is refed
if ( pObj->nRefs > 0 )
If_CutRef( p, pCut, IF_INFINITY );
+*/
}
/**Function*************************************************************
@@ -562,13 +564,7 @@ void If_ManImproveReduce( If_Man_t * p, int nLimit )
If_Obj_t * pObj;
int i;
If_ManForEachNode( p, pObj, i )
- {
- if ( 278 == i )
- {
- int s = 0;
- }
If_ManImproveNodeReduce( p, pObj, nLimit );
- }
}
////////////////////////////////////////////////////////////////////////
diff --git a/src/map/if/ifSeq.c b/src/map/if/ifSeq.c
index cd90a313..e6528233 100644
--- a/src/map/if/ifSeq.c
+++ b/src/map/if/ifSeq.c
@@ -24,19 +24,13 @@
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
-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 ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
- Synopsis [Performs sequential mapping.]
+ Synopsis [Prepares for sequential mapping by linking the latches.]
Description []
@@ -45,102 +39,46 @@ static int If_ObjPerformMappingLatch( If_Man_t * p, If_Obj_t * pObj );
SeeAlso []
***********************************************************************/
-int If_ManPerformMappingSeq( If_Man_t * p )
+void If_ManPrepareMappingSeq( If_Man_t * p )
{
- 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;
- p->nAttempts = 0;
- p->nMaxIters = 50;
- p->Period = (int)p->RequiredGlo;
-
- // make sure the clock period words
- if ( !If_ManBinarySearchPeriod( p, Mode ) )
- {
- printf( "If_ManPerformMappingSeq(): The upper bound on the clock period cannot be computed.\n" );
- return 0;
- }
-
- // perform binary search
- PeriodBest = If_ManBinarySearch_rec( p, Mode, 0, p->Period );
+ If_Obj_t * pObjLi, * pObjLo;
+ int i;
- // recompute the best l-values
- if ( p->Period != PeriodBest )
- {
- 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( "iscas/seqmap__stats.txt", "a+" );
- fprintf( pTable, "%d ", p->Period );
- fprintf( pTable, "\n" );
- fclose( pTable );
- }
-*/
- // print the result
- if ( p->pPars->fLiftLeaves )
+ // link the latch outputs (CIs) directly to the drivers of latch inputs (COs)
+ for ( i = 0; i < p->pPars->nLatches; i++ )
{
-// 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;
+ pObjLi = If_ManLi( p, i );
+ pObjLo = If_ManLo( p, i );
+ pObjLo->pFanin0 = If_ObjFanin0( pObjLi );
+ pObjLo->fCompl0 = If_ObjFaninC0( pObjLi );
}
-// if ( p->pPars->fVerbose )
- printf( "The best clock period is %3d.\n", p->Period );
- return 1;
}
/**Function*************************************************************
- Synopsis [Performs binary search for the optimal clock period.]
+ Synopsis [Collects latches in the topological order.]
- Description [Assumes that FiMin is infeasible while FiMax is feasible.]
+ Description []
SideEffects []
SeeAlso []
-
+
***********************************************************************/
-int If_ManBinarySearch_rec( If_Man_t * p, int Mode, int FiMin, int FiMax )
+void If_ManCollectLatches_rec( If_Obj_t * pObj, Vec_Ptr_t * vLatches )
{
- 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
+ if ( !If_ObjIsLatch(pObj) )
+ return;
+ if ( pObj->fMark )
+ return;
+ pObj->fMark = 1;
+ If_ManCollectLatches_rec( pObj->pFanin0, vLatches );
+ Vec_PtrPush( vLatches, pObj );
}
/**Function*************************************************************
- Synopsis [Returns 1 if retiming with this clock period is feasible.]
+ Synopsis [Collects latches in the topological order.]
Description []
@@ -149,66 +87,20 @@ int If_ManBinarySearch_rec( If_Man_t * p, int Mode, int FiMin, int FiMax )
SeeAlso []
***********************************************************************/
-int If_ManBinarySearchPeriod( If_Man_t * p, int Mode )
+Vec_Ptr_t * If_ManCollectLatches( If_Man_t * p )
{
+ Vec_Ptr_t * vLatches;
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? 0/*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;
+ int i;
+ // collect latches
+ vLatches = Vec_PtrAlloc( p->pPars->nLatches );
+ If_ManForEachLatchOutput( p, pObj, i )
+ 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*************************************************************
@@ -223,49 +115,53 @@ int If_ManBinarySearchPeriod( If_Man_t * p, int Mode )
SeeAlso []
***********************************************************************/
-int If_ManPerformMappingRoundSeq( If_Man_t * p, int Mode, int nIter, char * pLabel )
+int If_ManPerformMappingRoundSeq( If_Man_t * p, int nIter )
{
- 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_ObjPerformMappingAnd( p, pObj, 0, 0 );
if ( pObj->fRepr )
- If_ObjPerformMappingChoice( p, pObj, Mode );
- // check if updating happens
+ If_ObjPerformMappingChoice( p, pObj, 0, 0 );
+ }
+
+ // postprocess the mapping
+//printf( "Itereation %d: \n", nIter );
+ If_ManForEachNode( p, pObj, i )
+ {
+ // update the LValues stored separately
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) );
+//printf( "%d ", (int)If_ObjLValue(pObj) );
+ // reset the visit counters
+ assert( pObj->nVisits == 0 );
+ pObj->nVisits = pObj->nVisitsCopy;
}
- if ( !p->pPars->fVerbose )
- Extra_ProgressBarStop( pProgress );
- // propagate arrival times from the registers
+//printf( "\n" );
+
+ // propagate LValues over the registers
Vec_PtrForEachEntry( p->vLatchOrder, pObj, i )
- fChange |= If_ObjPerformMappingLatch( p, pObj );
-//printf( "\n\n" );
+ {
+ If_ObjSetLValue( pObj, If_ObjLValue(If_ObjFanin0(pObj)) - p->Period );
+ If_ObjSetArrTime( pObj, If_ObjLValue(pObj) );
+ }
+
// 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) );
+ p->AreaGlo = If_ManScanMapping(p);
+ printf( "S%d: Fi = %6.2f. Del = %6.2f. Area = %8.2f. Cuts = %8d. ",
+ nIter, (float)p->Period, p->RequiredGlo, p->AreaGlo, p->nCutsMerged );
PRT( "T", clock() - clk );
}
return fChange;
@@ -273,56 +169,96 @@ int If_ManPerformMappingRoundSeq( If_Man_t * p, int Mode, int nIter, char * pLab
/**Function*************************************************************
- Synopsis [Collects latches in the topological order.]
+ Synopsis [Returns 1 if retiming with this clock period is feasible.]
Description []
SideEffects []
SeeAlso []
-
+
***********************************************************************/
-void If_ManCollectLatches_rec( If_Obj_t * pObj, Vec_Ptr_t * vLatches )
+int If_ManBinarySearchPeriod( If_Man_t * p )
{
- if ( !If_ObjIsLatch(pObj) )
- return;
- if ( pObj->fMark )
- return;
- pObj->fMark = 1;
- If_ManCollectLatches_rec( pObj->pFanin0, vLatches );
- Vec_PtrPush( vLatches, pObj );
+ If_Obj_t * pObj;
+ int i, c, fConverged;
+ int fResetRefs = 0;
+
+ p->nAttempts++;
+
+ // set LValues of of PIs to be 0 and other nodes to be -infinity
+ // LValues of the PIs are already set to 0
+ // undo any previous mapping, except for CIs
+ If_ManForEachObj( p, pObj, i )
+ {
+ if ( If_ObjIsPi(pObj) || If_ObjIsConst1(pObj) )
+ If_ObjSetLValue( pObj, (float)0.0 );
+ else
+ If_ObjSetLValue( pObj, (float)-IF_INFINITY );
+ if ( If_ObjIsAnd(pObj) )
+ If_ObjCutBest(pObj)->nLeaves = 0;
+ }
+
+ // update all values iteratively
+ fConverged = 0;
+ for ( c = 1; c <= p->nMaxIters; c++ )
+ {
+ if ( !If_ManPerformMappingRoundSeq( p, c ) )
+ {
+ p->RequiredGlo = If_ManDelayMax( p, 1 );
+ fConverged = 1;
+ break;
+ }
+ p->RequiredGlo = If_ManDelayMax( p, 1 );
+//printf( "Global = %d \n", (int)p->RequiredGlo );
+ if ( p->RequiredGlo > p->Period + p->fEpsilon )
+ break;
+ }
+
+ // report the results
+ if ( p->pPars->fVerbose )
+ {
+ p->AreaGlo = 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 [Collects latches in the topological order.]
+ Synopsis [Performs binary search for the optimal clock period.]
- Description []
+ Description [Assumes that FiMin is infeasible while FiMax is feasible.]
SideEffects []
SeeAlso []
***********************************************************************/
-Vec_Ptr_t * If_ManCollectLatches( If_Man_t * p )
+int If_ManBinarySearch_rec( If_Man_t * p, int FiMin, int FiMax )
{
- 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;
+ assert( FiMin < FiMax );
+ if ( FiMin + 1 == FiMax )
+ return FiMax;
+ // compute the median
+ p->Period = FiMin + (FiMax - FiMin)/2;
+ if ( If_ManBinarySearchPeriod( p ) )
+ return If_ManBinarySearch_rec( p, FiMin, p->Period ); // Median is feasible
+ else
+ return If_ManBinarySearch_rec( p, p->Period, FiMax ); // Median is infeasible
}
/**Function*************************************************************
- Synopsis [Prepares for sequential mapping by linking the latches.]
+ Synopsis [Performs sequential mapping.]
Description []
@@ -331,45 +267,53 @@ Vec_Ptr_t * If_ManCollectLatches( If_Man_t * p )
SeeAlso []
***********************************************************************/
-int If_ManPrepareMappingSeq( If_Man_t * p )
+void If_ManPerformMappingSeqPost( If_Man_t * p )
{
- If_Obj_t * pObj, * pObjLi, * pObjLo, * pTemp;
- If_Cut_t * pCut;
+ If_Obj_t * pObjLi, * pObjLo, * pObj;
int i;
- // link the latch outputs (PIs) directly to the drivers of latch inputs (POs)
+
+ // link the latch outputs (CIs) directly to the drivers of latch inputs (COs)
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;
+ pObjLi = If_ManLi( p, i );
+ pObjLo = If_ManLo( p, i );
+// printf( "%3d : %2d -> %2d \n", i,
+// (int)If_ObjLValue(If_ObjFanin0(pObjLo)), (int)If_ObjLValue(pObjLo) );
}
- // collect latches
- p->vLatchOrder = If_ManCollectLatches( p );
- // propagate elementary cuts
- if ( p->pPars->fLiftLeaves )
+
+ // set arrival times
+ assert( p->pPars->pTimesArr != NULL );
+ If_ManForEachLatchOutput( p, pObjLo, i )
+ p->pPars->pTimesArr[i] = If_ObjLValue(pObjLo);
+
+ // set the required times
+ assert( p->pPars->pTimesReq == NULL );
+ p->pPars->pTimesReq = ALLOC( float, If_ManCoNum(p) );
+ If_ManForEachPo( p, pObj, i )
{
- 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;
-
- // there is a bug here, which shows when there are choices...
-// pTemp = If_ManObj(p, pCut->pLeaves[0] >> 8);
- pTemp = If_ManObj(p, pCut->pLeaves[0]);
- assert( !If_ObjIsLatch(pTemp) );
- }
+ p->pPars->pTimesReq[i] = p->RequiredGlo2;
+// printf( "Out %3d : %2d \n", i, (int)p->pPars->pTimesReq[i] );
}
- return 1;
+ If_ManForEachLatchInput( p, pObjLi, i )
+ {
+ p->pPars->pTimesReq[i] = If_ObjLValue(If_ObjFanin0(pObjLi));
+// printf( "Out %3d : %2d \n", i, (int)p->pPars->pTimesReq[i] );
+ }
+
+ // undo previous mapping
+ If_ManForEachObj( p, pObj, i )
+ if ( If_ObjIsAnd(pObj) )
+ If_ObjCutBest(pObj)->nLeaves = 0;
+
+ // map again combinationally
+ p->pPars->fSeqMap = 0;
+ If_ManPerformMappingComb( p );
+ p->pPars->fSeqMap = 1;
}
/**Function*************************************************************
- Synopsis [Performs mapping of the latches.]
+ Synopsis [Performs sequential mapping.]
Description []
@@ -378,34 +322,60 @@ int If_ManPrepareMappingSeq( If_Man_t * p )
SeeAlso []
***********************************************************************/
-int If_ObjPerformMappingLatch( If_Man_t * p, If_Obj_t * pObj )
+int If_ManPerformMappingSeq( If_Man_t * p )
{
- 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 )
+ int clkTotal = clock();
+ int PeriodBest;
+
+ p->SortMode = 0;
+
+ // perform combinational mapping to get the upper bound on the clock period
+ If_ManPerformMappingRound( p, 1, 0, 0, NULL );
+ p->RequiredGlo = If_ManDelayMax( p, 0 );
+ p->RequiredGlo2 = p->RequiredGlo;
+
+ // set direct linking of latches with their inputs
+ If_ManPrepareMappingSeq( p );
+
+ // collect latches
+ p->vLatchOrder = If_ManCollectLatches( p );
+
+ // set parameters
+ p->nCutsUsed = p->pPars->nCutsMax;
+ p->nAttempts = 0;
+ p->nMaxIters = 50;
+ p->Period = (int)p->RequiredGlo;
+
+ // make sure the clock period works
+ if ( !If_ManBinarySearchPeriod( p ) )
{
- pObj->nCuts = 1;
- If_ObjSetLValue( pObj, If_ObjLValue(pFanin) - p->Period );
+ printf( "If_ManPerformMappingSeq(): The upper bound on the clock period cannot be computed.\n" );
+ return 0;
}
- else
+
+ // perform binary search
+ PeriodBest = If_ManBinarySearch_rec( p, 0, p->Period );
+
+ // recompute the best l-values
+ if ( p->Period != PeriodBest )
{
- pObj->nCuts = pFanin->nCuts;
- If_ObjForEachCut( pObj, pCut, i )
+ p->Period = PeriodBest;
+ if ( !If_ManBinarySearchPeriod( p ) )
{
- If_CutCopy( pCut, pFanin->Cuts + i );
- If_CutLift( pCut );
- pCut->Delay -= p->Period;
- pCut->fCompl ^= pObj->fCompl0;
+ printf( "If_ManPerformMappingSeq(): The final clock period cannot be confirmed.\n" );
+ return 0;
}
}
- return LValueOld != If_ObjLValue(pObj);
+ if ( p->pPars->fVerbose )
+ {
+ printf( "The best clock period is %3d. ", p->Period );
+ PRT( "Sequential time", clock() - clkTotal );
+ }
+ p->RequiredGlo = (float)PeriodBest;
+
+ // postprocess it using combinational mapping
+ If_ManPerformMappingSeqPost( p );
+ return 1;
}
////////////////////////////////////////////////////////////////////////
diff --git a/src/map/if/ifUtil.c b/src/map/if/ifUtil.c
index 1fd3229d..4fdb4d31 100644
--- a/src/map/if/ifUtil.c
+++ b/src/map/if/ifUtil.c
@@ -61,11 +61,9 @@ void If_ManCleanNodeCopy( If_Man_t * p )
void If_ManCleanCutData( If_Man_t * p )
{
If_Obj_t * pObj;
- If_Cut_t * pCut;
- int i, k;
+ int i;
If_ManForEachObj( p, pObj, i )
- If_ObjForEachCut( pObj, pCut, k )
- If_CutSetData( pCut, NULL );
+ If_CutSetData( If_ObjCutBest(pObj), NULL );
}
/**Function*************************************************************
@@ -113,20 +111,20 @@ float If_ManDelayMax( If_Man_t * p, int 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;
+ if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) )
+ DelayBest = If_ObjArrTime(If_ObjFanin0(pObj));
}
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;
+ If_ManForEachLatchInput( p, pObj, i )
+ if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) )
+ DelayBest = If_ObjArrTime(If_ObjFanin0(pObj));
}
else
{
If_ManForEachCo( p, pObj, i )
- if ( DelayBest < If_ObjCutBest( If_ObjFanin0(pObj) )->Delay )
- DelayBest = If_ObjCutBest( If_ObjFanin0(pObj) )->Delay;
+ if ( DelayBest < If_ObjArrTime(If_ObjFanin0(pObj)) )
+ DelayBest = If_ObjArrTime(If_ObjFanin0(pObj));
}
return DelayBest;
}
@@ -142,40 +140,67 @@ float If_ManDelayMax( If_Man_t * p, int fSeq )
SeeAlso []
***********************************************************************/
-void If_ManComputeRequired( If_Man_t * p, int fFirstTime )
+void If_ManComputeRequired( If_Man_t * p )
{
If_Obj_t * pObj;
int i;
+
// compute area, clean required times, collect nodes used in the mapping
p->nNets = 0;
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 )
+
+ // consider the case when the required times are given
+ if ( p->pPars->pTimesReq )
{
- 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 )
+ assert( !p->pPars->fAreaOnly );
+ // make sure that the required time hold
+ If_ManForEachCo( p, pObj, i )
{
- 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;
+ if ( If_ObjArrTime(If_ObjFanin0(pObj)) > p->pPars->pTimesReq[i] + p->fEpsilon )
+ printf( "Required times are violated for output %d (arr = %d; req = %d).\n",
+ i, (int)If_ObjArrTime(If_ObjFanin0(pObj)), (int)p->pPars->pTimesReq[i] );
+ If_ObjFanin0(pObj)->Required = p->pPars->pTimesReq[i];
}
}
- // 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;
+ // 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 ( p->fNextRound == 0 )
+ {
+ p->fNextRound = 1;
+ 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 ( p->fNextRound == 0 )
+ {
+ p->fNextRound = 1;
+ printf( "Relaxing the required times from (%4.2f) to the target (%4.2f).\n", p->RequiredGlo, p->pPars->DelayTarget );
+ }
+ p->RequiredGlo = p->pPars->DelayTarget;
+ }
+ }
+ // do not propagate required times if area minimization is requested
+ if ( p->pPars->fAreaOnly )
+ return;
+ // set the required times for the POs
+ if ( p->pPars->fLatchPaths )
+ {
+ If_ManForEachLatchInput( 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 )
@@ -236,7 +261,8 @@ float If_ManScanMapping( If_Man_t * p )
If_ManForEachObj( p, pObj, i )
{
pObj->Required = IF_FLOAT_LARGE;
- pObj->nRefs = 0;
+ pObj->nVisits = pObj->nVisitsCopy;
+ pObj->nRefs = 0;
}
// allocate place to store the nodes
ppStore = ALLOC( If_Obj_t *, p->nLevelMax + 1 );
@@ -318,6 +344,83 @@ float If_ManScanMappingSeq( If_Man_t * p )
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 []
+
+***********************************************************************/
+void If_ManResetOriginalRefs( If_Man_t * p )
+{
+ If_Obj_t * pObj;
+ int i;
+ If_ManForEachObj( p, pObj, i )
+ pObj->nRefs = 0;
+ If_ManForEachObj( p, pObj, i )
+ {
+ if ( If_ObjIsAnd(pObj) )
+ {
+ pObj->pFanin0->nRefs++;
+ pObj->pFanin1->nRefs++;
+ }
+ else if ( If_ObjIsCo(pObj) )
+ pObj->pFanin0->nRefs++;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes cross-cut of the circuit.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int If_ManCrossCut( If_Man_t * p )
+{
+ If_Obj_t * pObj, * pFanin;
+ int i, nCutSize = 0, nCutSizeMax = 0;
+ If_ManForEachObj( p, pObj, i )
+ {
+ if ( !If_ObjIsAnd(pObj) )
+ continue;
+ // consider the node
+ if ( nCutSizeMax < ++nCutSize )
+ nCutSizeMax = nCutSize;
+ if ( pObj->nVisits == 0 )
+ nCutSize--;
+ // consider the fanins
+ pFanin = If_ObjFanin0(pObj);
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ nCutSize--;
+ pFanin = If_ObjFanin1(pObj);
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ nCutSize--;
+ // consider the choice class
+ if ( pObj->fRepr )
+ for ( pFanin = pObj; pFanin; pFanin = pFanin->pEquiv )
+ if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
+ nCutSize--;
+ }
+ If_ManForEachObj( p, pObj, i )
+ {
+ assert( If_ObjIsCi(pObj) || pObj->fVisit == 0 );
+ pObj->nVisits = pObj->nVisitsCopy;
+ }
+ assert( nCutSize == 0 );
+// printf( "Max cross cut size = %6d.\n", nCutSizeMax );
+ return nCutSizeMax;
+}
+
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
diff --git a/src/map/if/module.make b/src/map/if/module.make
index c4fa56cb..f3d189be 100644
--- a/src/map/if/module.make
+++ b/src/map/if/module.make
@@ -2,7 +2,6 @@ SRC += src/map/if/ifCore.c \
src/map/if/ifCut.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 \
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-05 22:51:49 +0000