summaryrefslogtreecommitdiffstats
path: root/src/map/mapper
diff options
context:
space:
mode:
Diffstat (limited to 'src/map/mapper')
-rw-r--r--src/map/mapper/mapper.h2
-rw-r--r--src/map/mapper/mapperCanon.c89
-rw-r--r--src/map/mapper/mapperCore.c1
-rw-r--r--src/map/mapper/mapperCreate.c16
-rw-r--r--src/map/mapper/mapperCut.c182
-rw-r--r--src/map/mapper/mapperFanout.c4
-rw-r--r--src/map/mapper/mapperInt.h29
-rw-r--r--src/map/mapper/mapperRefs.c43
-rw-r--r--src/map/mapper/mapperTime.c4
-rw-r--r--src/map/mapper/mapperTruth.c24
-rw-r--r--src/map/mapper/mapperUtils.c142
11 files changed, 300 insertions, 236 deletions
diff --git a/src/map/mapper/mapper.h b/src/map/mapper/mapper.h
index 9ef8ee17..1322cdfa 100644
--- a/src/map/mapper/mapper.h
+++ b/src/map/mapper/mapper.h
@@ -152,8 +152,8 @@ extern void Map_NodeSetChoice( Map_Man_t * pMan, Map_Node_t * pNodeOl
/*=== resmCanon.c =============================================================*/
extern int Map_CanonComputeSlow( unsigned uTruths[][2], int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] );
+extern int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] );
/*=== mapperCut.c =============================================================*/
-extern void Map_MappingCreatePiCuts( Map_Man_t * p );
extern Map_Cut_t * Map_CutAlloc( Map_Man_t * p );
/*=== mapperCutUtils.c =============================================================*/
extern void Map_CutCreateFromNode( Map_Man_t * p, Map_Super_t * pSuper, int iRoot, unsigned uPhaseRoot,
diff --git a/src/map/mapper/mapperCanon.c b/src/map/mapper/mapperCanon.c
index c5186c7e..4937fd0e 100644
--- a/src/map/mapper/mapperCanon.c
+++ b/src/map/mapper/mapperCanon.c
@@ -154,6 +154,95 @@ void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[]
}
}
+/**Function*************************************************************
+
+ Synopsis [Computes the N-canonical form of the Boolean function.]
+
+ Description [The N-canonical form is defined as the truth table with
+ the minimum integer value. This function exhaustively enumerates
+ through the complete set of 2^N phase assignments.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] )
+{
+ unsigned uTruth0, uTruth1;
+ unsigned uCanon0, uCanon1, uCanonBest;
+ int i, Limit;
+
+ if ( nVarsMax != 5 || nVarsReal < 5 )
+ return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
+
+ assert( nVarsMax == 5 );
+ uTruth0 = uTruth[0] & 0xFFFF;
+ uTruth1 = (uTruth[0] >> 16);
+ if ( uTruth1 == 0 )
+ {
+ uTruthRes[0] = p->uCanons[uTruth0];
+ uTruthRes[1] = uTruthRes[0];
+ Limit = (p->pCounters[uTruth0] > 4)? 4 : p->pCounters[uTruth0];
+ for ( i = 0; i < Limit; i++ )
+ puPhases[i] = p->uPhases[uTruth0][i];
+ return Limit;
+ }
+ else if ( uTruth0 == 0 )
+ {
+ uTruthRes[0] = p->uCanons[uTruth1];
+ uTruthRes[1] = uTruthRes[0];
+ Limit = (p->pCounters[uTruth1] > 4)? 4 : p->pCounters[uTruth1];
+ for ( i = 0; i < Limit; i++ )
+ {
+ puPhases[i] = p->uPhases[uTruth1][i];
+ puPhases[i] |= (1 << 4);
+ }
+ return Limit;
+ }
+ uCanon0 = p->uCanons[uTruth0];
+ uCanon1 = p->uCanons[uTruth1];
+ if ( uCanon0 && uCanon1 && uCanon0 > uCanon1 ) // using nCanon1 as the main one
+ {
+ assert( p->pCounters[uTruth1] > 0 );
+ uCanonBest = 0xFFFF;
+ for ( i = 0; i < p->pCounters[uTruth1]; i++ )
+ {
+ uCanon0 = Extra_TruthPolarize( uTruth0, p->uPhases[uTruth1][i], 4 );
+ if ( uCanonBest > uCanon0 )
+ uCanonBest = uCanon0;
+ }
+ uTruthRes[0] = (uCanon1 << 16) | uCanonBest;
+ uTruthRes[1] = uTruthRes[0];
+ Limit = (p->pCounters[uTruth1] > 4)? 4 : p->pCounters[uTruth1];
+ for ( i = 0; i < Limit; i++ )
+ puPhases[i] = p->uPhases[uTruth1][i];
+ return Limit;
+ }
+ else if ( uCanon0 && uCanon1 && uCanon0 < uCanon1 )
+ {
+ assert( p->pCounters[uTruth0] > 0 );
+ uCanonBest = 0xFFFF;
+ for ( i = 0; i < p->pCounters[uTruth0]; i++ )
+ {
+ uCanon1 = Extra_TruthPolarize( uTruth1, p->uPhases[uTruth0][i], 4 );
+ if ( uCanonBest > uCanon1 )
+ uCanonBest = uCanon1;
+ }
+ uTruthRes[0] = (uCanon0 << 16) | uCanonBest;
+ uTruthRes[1] = uTruthRes[0];
+ Limit = (p->pCounters[uTruth0] > 4)? 4 : p->pCounters[uTruth0];
+ for ( i = 0; i < Limit; i++ )
+ {
+ puPhases[i] = p->uPhases[uTruth0][i];
+ puPhases[i] |= (1 << 4);
+ }
+ return Limit;
+ }
+ else
+ return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
+}
+
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
diff --git a/src/map/mapper/mapperCore.c b/src/map/mapper/mapperCore.c
index 0014d48f..16cbfd5c 100644
--- a/src/map/mapper/mapperCore.c
+++ b/src/map/mapper/mapperCore.c
@@ -69,6 +69,7 @@ int Map_Mapping( Map_Man_t * p )
Map_MappingTruths( p );
p->timeTruth = clock() - clk;
//////////////////////////////////////////////////////////////////////
+//PRT( "Truths", clock() - clk );
//////////////////////////////////////////////////////////////////////
// compute the minimum-delay mapping
diff --git a/src/map/mapper/mapperCreate.c b/src/map/mapper/mapperCreate.c
index eb938847..dc056f34 100644
--- a/src/map/mapper/mapperCreate.c
+++ b/src/map/mapper/mapperCreate.c
@@ -196,6 +196,9 @@ Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose )
p->fEpsilon = (float)0.001;
assert( p->nVarsMax > 0 );
+ if ( p->nVarsMax == 5 )
+ Extra_Truth4VarN( &p->uCanons, &p->uPhases, &p->pCounters, 16 );
+
// start various data structures
Map_TableCreate( p );
Map_MappingSetupTruthTables( p->uTruths );
@@ -211,8 +214,6 @@ Map_Man_t * Map_ManCreate( int nInputs, int nOutputs, int fVerbose )
p->vNodesAll = Map_NodeVecAlloc( 100 );
p->vNodesTemp = Map_NodeVecAlloc( 100 );
p->vMapping = Map_NodeVecAlloc( 100 );
- p->vInside = Map_NodeVecAlloc( 100 );
- p->vFanins = Map_NodeVecAlloc( 100 );
p->vVisited = Map_NodeVecAlloc( 100 );
// create the PI nodes
@@ -245,10 +246,6 @@ void Map_ManFree( Map_Man_t * p )
// for ( i = 0; i < p->vNodesAll->nSize; i++ )
// Map_NodeVecFree( p->vNodesAll->pArray[i]->vFanouts );
// Map_NodeVecFree( p->pConst1->vFanouts );
- if ( p->vInside )
- Map_NodeVecFree( p->vInside );
- if ( p->vFanins )
- Map_NodeVecFree( p->vFanins );
if ( p->vAnds )
Map_NodeVecFree( p->vAnds );
if ( p->vNodesAll )
@@ -259,6 +256,9 @@ void Map_ManFree( Map_Man_t * p )
Map_NodeVecFree( p->vMapping );
if ( p->vVisited )
Map_NodeVecFree( p->vVisited );
+ if ( p->uCanons ) free( p->uCanons );
+ if ( p->uPhases ) free( p->uPhases );
+ if ( p->pCounters ) free( p->pCounters );
Extra_MmFixedStop( p->mmNodes, 0 );
Extra_MmFixedStop( p->mmCuts, 0 );
FREE( p->pInputArrivals );
@@ -266,8 +266,6 @@ void Map_ManFree( Map_Man_t * p )
FREE( p->pOutputs );
FREE( p->pBins );
FREE( p->ppOutputNames );
- if ( p->pSimInfo ) FREE( p->pSimInfo[0] );
- FREE( p->pSimInfo );
FREE( p );
}
@@ -357,9 +355,11 @@ Map_Node_t * Map_NodeCreate( Map_Man_t * p, Map_Node_t * p1, Map_Node_t * p2 )
// set the level of this node
if ( p1 )
{
+#ifdef MAP_ALLOCATE_FANOUT
// create the fanout info
Map_NodeAddFaninFanout( Map_Regular(p1), pNode );
Map_NodeAddFaninFanout( Map_Regular(p2), pNode );
+#endif
pNode->Level = 1 + MAP_MAX(Map_Regular(pNode->p1)->Level, Map_Regular(pNode->p2)->Level);
pNode->fInv = Map_NodeIsSimComplement(p1) & Map_NodeIsSimComplement(p2);
}
diff --git a/src/map/mapper/mapperCut.c b/src/map/mapper/mapperCut.c
index 1f3c8074..0c3a0910 100644
--- a/src/map/mapper/mapperCut.c
+++ b/src/map/mapper/mapperCut.c
@@ -65,6 +65,7 @@ static Map_Cut_t * Map_CutSortCuts( Map_Man_t * pMan, Map_CutTable_t * p, M
static int Map_CutList2Array( Map_Cut_t ** pArray, Map_Cut_t * pList );
static Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts );
+static unsigned Map_CutComputeTruth( Map_Man_t * p, Map_Cut_t * pCut, Map_Cut_t * pTemp0, Map_Cut_t * pTemp1, int fComp0, int fComp1 );
// iterator through all the cuts of the list
#define Map_ListForEachCut( pList, pCut ) \
@@ -78,7 +79,6 @@ static Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts );
pCut = pCut2, \
pCut2 = pCut? pCut->pNext: NULL )
-
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFITIONS ///
////////////////////////////////////////////////////////////////////////
@@ -114,6 +114,7 @@ void Map_MappingCuts( Map_Man_t * p )
Map_Node_t * pNode;
Map_Cut_t * pCut;
int nCuts, nNodes, i;
+ int clk = clock();
// set the elementary cuts for the PI variables
assert( p->nVarsMax > 1 && p->nVarsMax < 7 );
for ( i = 0; i < p->nInputs; i++ )
@@ -121,10 +122,10 @@ void Map_MappingCuts( Map_Man_t * p )
pCut = Map_CutAlloc( p );
pCut->nLeaves = 1;
pCut->ppLeaves[0] = p->pInputs[i];
-// pCut->fLevel = (float)pCut->ppLeaves[0]->Level;
p->pInputs[i]->pCuts = pCut;
p->pInputs[i]->pCutBest[0] = NULL; // negative polarity is not mapped
p->pInputs[i]->pCutBest[1] = pCut; // positive polarity is a trivial cut
+ pCut->uTruth = 0xAAAAAAAA; // the first variable "10101010"
pCut->M[0].AreaFlow = 0.0;
pCut->M[1].AreaFlow = 0.0;
}
@@ -148,8 +149,9 @@ void Map_MappingCuts( Map_Man_t * p )
if ( p->fVerbose )
{
nCuts = Map_MappingCountAllCuts(p);
- printf( "Nodes = %6d. Total %d-feasible cuts = %d. Cuts per node = %.1f.\n",
+ printf( "Nodes = %6d. Total %d-feasible cuts = %d. Per node = %.1f. ",
p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes );
+ PRT( "Time", clock() - clk );
}
// print the cuts for the first primary output
@@ -158,48 +160,6 @@ void Map_MappingCuts( Map_Man_t * p )
/**Function*************************************************************
- Synopsis [Performs technology mapping for variable-size-LUTs.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void Map_MappingCreatePiCuts( Map_Man_t * p )
-{
- Map_Cut_t * pCut;
- int i;
-
- // set the elementary cuts for the PI variables
- for ( i = 0; i < p->nInputs; i++ )
- {
- pCut = Map_CutAlloc( p );
- pCut->nLeaves = 1;
- pCut->ppLeaves[0] = p->pInputs[i];
-// pCut->fLevel = (float)pCut->ppLeaves[0]->Level;
- p->pInputs[i]->pCuts = pCut;
- p->pInputs[i]->pCutBest[1] = pCut;
- p->pInputs[i]->pCutBest[0] = pCut;
- // set the input arrival times
-// p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i];
-
- // set the input arrival times
- pCut = p->pInputs[i]->pCutBest[1];
- pCut->M[1].tArrive = p->pInputArrivals[i];
- pCut->M[1].tArrive.Worst = MAP_MAX( pCut->M[1].tArrive.Rise, pCut->M[1].tArrive.Fall );
- // set the arrival times of the negative phases of the PI nodes
- pCut = p->pInputs[i]->pCutBest[0];
- pCut->M[0].tArrive.Rise = p->pInputArrivals[i].Fall + p->pSuperLib->tDelayInv.Rise;
- pCut->M[0].tArrive.Fall = p->pInputArrivals[i].Rise + p->pSuperLib->tDelayInv.Fall;
- pCut->M[0].tArrive.Worst = MAP_MAX( pCut->M[0].tArrive.Rise, pCut->M[0].tArrive.Fall );
-
- }
-}
-
-/**Function*************************************************************
-
Synopsis [Computes the cuts for one node.]
Description []
@@ -242,7 +202,7 @@ Map_Cut_t * Map_CutCompute( Map_Man_t * p, Map_CutTable_t * pTable, Map_Node_t *
pCut = Map_CutAlloc( p );
pCut->nLeaves = 1;
pCut->ppLeaves[0] = pNode;
-// pCut->fLevel = (float)pCut->ppLeaves[0]->Level;
+ pCut->uTruth = 0xAAAAAAAA;
// append (it is important that the elementary cut is appended first)
pCut->pNext = pList;
// set at the node
@@ -392,6 +352,8 @@ Map_Cut_t * Map_CutMergeLists( Map_Man_t * p, Map_CutTable_t * pTable,
// add data to the cut
pCut->pOne = Map_CutNotCond( pTemp1, fComp1 );
pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 );
+// if ( p->nVarsMax == 5 )
+// pCut->uTruth = Map_CutComputeTruth( p, pCut, pTemp1, pTemp2, fComp1, fComp2 );
// add it to the corresponding list
pCut->pNext = pLists[pCut->nLeaves];
pLists[pCut->nLeaves] = pCut;
@@ -424,6 +386,8 @@ Map_Cut_t * Map_CutMergeLists( Map_Man_t * p, Map_CutTable_t * pTable,
// add data to the cut
pCut->pOne = Map_CutNotCond( pTemp1, fComp1 );
pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 );
+// if ( p->nVarsMax == 5 )
+// pCut->uTruth = Map_CutComputeTruth( p, pCut, pTemp1, pTemp2, fComp1, fComp2 );
// add it to the corresponding list
pCut->pNext = pLists[pCut->nLeaves];
pLists[pCut->nLeaves] = pCut;
@@ -459,6 +423,8 @@ Map_Cut_t * Map_CutMergeLists( Map_Man_t * p, Map_CutTable_t * pTable,
// add data to the cut
pCut->pOne = Map_CutNotCond( pTemp1, fComp1 );
pCut->pTwo = Map_CutNotCond( pTemp2, fComp2 );
+// if ( p->nVarsMax == 5 )
+// pCut->uTruth = Map_CutComputeTruth( p, pCut, pTemp1, pTemp2, fComp1, fComp2 );
// add it to the corresponding list
pCut->pNext = pLists[pCut->nLeaves];
pLists[pCut->nLeaves] = pCut;
@@ -725,12 +691,26 @@ int Map_MappingCountAllCuts( Map_Man_t * pMan )
Map_Node_t * pNode;
Map_Cut_t * pCut;
int i, nCuts;
+// int nCuts55 = 0, nCuts5x = 0, nCuts4x = 0, nCuts3x = 0;
nCuts = 0;
for ( i = 0; i < pMan->nBins; i++ )
for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
if ( pCut->nLeaves > 1 ) // skip the elementary cuts
+ {
nCuts++;
+/*
+ if ( Map_CutRegular(pCut->pOne)->nLeaves == 5 && Map_CutRegular(pCut->pTwo)->nLeaves == 5 )
+ nCuts55++;
+ if ( Map_CutRegular(pCut->pOne)->nLeaves == 5 || Map_CutRegular(pCut->pTwo)->nLeaves == 5 )
+ nCuts5x++;
+ else if ( Map_CutRegular(pCut->pOne)->nLeaves == 4 || Map_CutRegular(pCut->pTwo)->nLeaves == 4 )
+ nCuts4x++;
+ else if ( Map_CutRegular(pCut->pOne)->nLeaves == 3 || Map_CutRegular(pCut->pTwo)->nLeaves == 3 )
+ nCuts3x++;
+*/
+ }
+// printf( "Total cuts = %6d. 55 = %6d. 5x = %6d. 4x = %6d. 3x = %6d.\n", nCuts, nCuts55, nCuts5x, nCuts4x, nCuts3x );
return nCuts;
}
@@ -926,7 +906,6 @@ Map_Cut_t * Map_CutTableConsider( Map_Man_t * pMan, Map_CutTable_t * p, Map_Node
Map_Cut_t * pCut;
int Place, i;
// int clk;
-
// check the cut
Place = Map_CutTableLookup( p, ppNodes, nNodes );
if ( Place == -1 )
@@ -937,13 +916,8 @@ Map_Cut_t * Map_CutTableConsider( Map_Man_t * pMan, Map_CutTable_t * p, Map_Node
pCut = Map_CutAlloc( pMan );
//pMan->time1 += clock() - clk;
pCut->nLeaves = nNodes;
-// pCut->fLevel = 0;
for ( i = 0; i < nNodes; i++ )
- {
pCut->ppLeaves[i] = ppNodes[i];
-// pCut->fLevel += ppNodes[i]->Level;
- }
-// pCut->fLevel /= nNodes;
// add the cut to the table
assert( p->pBins[Place] == NULL );
p->pBins[Place] = pCut;
@@ -994,12 +968,6 @@ int Map_CutSortCutsCompare( Map_Cut_t ** pC1, Map_Cut_t ** pC2 )
return -1;
if ( (*pC1)->nLeaves > (*pC2)->nLeaves )
return 1;
-/*
- if ( (*pC1)->fLevel < (*pC2)->fLevel )
- return -1;
- if ( (*pC1)->fLevel > (*pC2)->fLevel )
- return 1;
-*/
return 0;
}
@@ -1081,7 +1049,6 @@ Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts )
// connect these lists
*ppListNew = pArray[i];
ppListNew = &pArray[i]->pNext;
-//printf( " %d(%.2f)", pArray[i]->nLeaves, pArray[i]->fLevel );
}
//printf( "\n" );
@@ -1090,6 +1057,103 @@ Map_Cut_t * Map_CutArray2List( Map_Cut_t ** pArray, int nCuts )
}
+/**Function*************************************************************
+
+ Synopsis [Computes the truth table of the 5-input cut.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+unsigned Map_CutComputeTruth( Map_Man_t * p, Map_Cut_t * pCut, Map_Cut_t * pTemp0, Map_Cut_t * pTemp1, int fComp0, int fComp1 )
+{
+ static unsigned ** pPerms53 = NULL;
+ static unsigned ** pPerms54 = NULL;
+
+ unsigned uPhase, uTruth, uTruth0, uTruth1;
+ int i, k;
+
+ if ( pPerms53 == NULL )
+ {
+ pPerms53 = (unsigned **)Extra_TruthPerm53();
+ pPerms54 = (unsigned **)Extra_TruthPerm54();
+ }
+
+ // find the mapping from the old nodes to the new
+ if ( pTemp0->nLeaves == pCut->nLeaves )
+ uTruth0 = pTemp0->uTruth;
+ else
+ {
+ assert( pTemp0->nLeaves < pCut->nLeaves );
+ uPhase = 0;
+ for ( i = 0; i < (int)pTemp0->nLeaves; i++ )
+ {
+ for ( k = 0; k < pCut->nLeaves; k++ )
+ if ( pTemp0->ppLeaves[i] == pCut->ppLeaves[k] )
+ break;
+ uPhase |= (1 << k);
+ }
+ assert( uPhase < 32 );
+ if ( pTemp0->nLeaves == 4 )
+ {
+ if ( uPhase == 31-16 ) // 01111
+ uTruth0 = pTemp0->uTruth;
+ else if ( uPhase == 31-8 ) // 10111
+ uTruth0 = pPerms54[pTemp0->uTruth & 0xFFFF][0];
+ else if ( uPhase == 31-4 ) // 11011
+ uTruth0 = pPerms54[pTemp0->uTruth & 0xFFFF][1];
+ else if ( uPhase == 31-2 ) // 11101
+ uTruth0 = pPerms54[pTemp0->uTruth & 0xFFFF][2];
+ else if ( uPhase == 31-1 ) // 11110
+ uTruth0 = pPerms54[pTemp0->uTruth & 0xFFFF][3];
+ else
+ assert( 0 );
+ }
+ else
+ uTruth0 = pPerms53[pTemp0->uTruth & 0xFF][uPhase];
+ }
+ uTruth0 = fComp0? ~uTruth0: uTruth0;
+
+ // find the mapping from the old nodes to the new
+ if ( pTemp1->nLeaves == pCut->nLeaves )
+ uTruth1 = pTemp1->uTruth;
+ else
+ {
+ assert( pTemp1->nLeaves < pCut->nLeaves );
+ uPhase = 0;
+ for ( i = 0; i < (int)pTemp1->nLeaves; i++ )
+ {
+ for ( k = 0; k < pCut->nLeaves; k++ )
+ if ( pTemp1->ppLeaves[i] == pCut->ppLeaves[k] )
+ break;
+ uPhase |= (1 << k);
+ }
+ assert( uPhase < 32 );
+ if ( pTemp1->nLeaves == 4 )
+ {
+ if ( uPhase == 31-16 ) // 01111
+ uTruth1 = pTemp1->uTruth;
+ else if ( uPhase == 31-8 ) // 10111
+ uTruth1 = pPerms54[pTemp1->uTruth & 0xFFFF][0];
+ else if ( uPhase == 31-4 ) // 11011
+ uTruth1 = pPerms54[pTemp1->uTruth & 0xFFFF][1];
+ else if ( uPhase == 31-2 ) // 11101
+ uTruth1 = pPerms54[pTemp1->uTruth & 0xFFFF][2];
+ else if ( uPhase == 31-1 ) // 11110
+ uTruth1 = pPerms54[pTemp1->uTruth & 0xFFFF][3];
+ else
+ assert( 0 );
+ }
+ else
+ uTruth1 = pPerms53[pTemp1->uTruth & 0xFF][uPhase];
+ }
+ uTruth1 = fComp1? ~uTruth1: uTruth1;
+ uTruth = uTruth0 & uTruth1;
+ return uTruth;
+}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
diff --git a/src/map/mapper/mapperFanout.c b/src/map/mapper/mapperFanout.c
index 7bd92ed9..aca29918 100644
--- a/src/map/mapper/mapperFanout.c
+++ b/src/map/mapper/mapperFanout.c
@@ -18,6 +18,8 @@
#include "mapperInt.h"
+#ifdef MAP_ALLOCATE_FANOUT
+
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
@@ -26,7 +28,6 @@
/// FUNCTION DEFITIONS ///
////////////////////////////////////////////////////////////////////////
-
/**Function*************************************************************
Synopsis [Add the fanout to the node.]
@@ -136,4 +137,5 @@ int Map_NodeGetFanoutNum( Map_Node_t * pNode )
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
+#endif
diff --git a/src/map/mapper/mapperInt.h b/src/map/mapper/mapperInt.h
index d4262abb..7d63a804 100644
--- a/src/map/mapper/mapperInt.h
+++ b/src/map/mapper/mapperInt.h
@@ -36,7 +36,10 @@
////////////////////////////////////////////////////////////////////////
/// PARAMETERS ///
////////////////////////////////////////////////////////////////////////
-
+
+// uncomment to have fanouts represented in the mapping graph
+//#define MAP_ALLOCATE_FANOUT 1
+
////////////////////////////////////////////////////////////////////////
/// MACRO DEFITIONS ///
////////////////////////////////////////////////////////////////////////
@@ -123,18 +126,15 @@ struct Map_ManStruct_t_
int nCountsBest[32];// the counter of minterms
Map_NodeVec_t * vVisited; // the visited cuts during cut computation
- // simulation info from the FRAIG manager
- int nSimRounds; // the number of words in the simulation info
- unsigned ** pSimInfo; // the simulation info for each PI
-
- // don't-care computation
- Map_NodeVec_t * vInside; // the array of nodes for SDC computation
- Map_NodeVec_t * vFanins; // the array of nodes for SDC computation
-
// the memory managers
Extra_MmFixed_t * mmNodes; // the memory manager for nodes
Extra_MmFixed_t * mmCuts; // the memory manager for cuts
+ // precomputed N-canonical forms
+ unsigned short * uCanons; // N-canonical forms
+ char ** uPhases; // N-canonical phases
+ char * pCounters; // counters of phases
+
// various statistical variables
int nChoiceNodes; // the number of choice nodes
int nChoices; // the number of all choices
@@ -211,27 +211,25 @@ struct Map_NodeStruct_t_
int nRefAct[3]; // estimated fanout for current covering phase, neg and pos and sum
float nRefEst[3]; // actual fanout for previous covering phase, neg and pos and sum
- // the successors of this node
+ // connectivity
Map_Node_t * p1; // the first child
Map_Node_t * p2; // the second child
Map_Node_t * pNextE; // the next functionally equivalent node
Map_Node_t * pRepr; // the representative of the functionally equivalent class
-// Map_NodeVec_t * vFanouts; // the array of fanouts of the node
+#ifdef MAP_ALLOCATE_FANOUT
// representation of node's fanouts
Map_Node_t * pFanPivot; // the first fanout of this node
Map_Node_t * pFanFanin1; // the next fanout of p1
Map_Node_t * pFanFanin2; // the next fanout of p2
-
- unsigned * pSims; // the simulation info
- float SwitchProb; // the switching probability
+// Map_NodeVec_t * vFanouts; // the array of fanouts of the gate
+#endif
// the delay information
Map_Time_t tArrival[2]; // the best arrival time of the neg (0) and pos (1) phases
Map_Time_t tRequired[2]; // the required time of the neg (0) and pos (1) phases
// misc information
- Map_Cut_t * pCutOld[2]; // the old mapping for neg and pos phase
Map_Cut_t * pCutBest[2]; // the best mapping for neg and pos phase
Map_Cut_t * pCuts; // mapping choices for the node (elementary comes first)
char * pData0; // temporary storage for the corresponding network node
@@ -259,6 +257,7 @@ struct Map_CutStruct_t_
Map_Cut_t * pOne; // the father of this cut
Map_Cut_t * pTwo; // the mother of this cut
Map_Node_t * ppLeaves[6]; // the leaves of this cut
+ unsigned uTruth; // truth table for five-input cuts
char nLeaves; // the number of leaves
char nVolume; // the volume of this cut
char fMark; // the mark to denote visited cut
diff --git a/src/map/mapper/mapperRefs.c b/src/map/mapper/mapperRefs.c
index 334e98c7..e74bab9a 100644
--- a/src/map/mapper/mapperRefs.c
+++ b/src/map/mapper/mapperRefs.c
@@ -25,7 +25,7 @@
static int Map_NodeIncRefPhaseAct( Map_Node_t * pNode, int fPhase );
static int Map_NodeDecRefPhaseAct( Map_Node_t * pNode, int fPhase );
static float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference );
-static void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode );
+static void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode, Map_Node_t ** ppStore );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFITIONS ///
@@ -401,8 +401,9 @@ float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference )
Synopsis [Computes actual reference counters.]
- Description [Stores all the nodes used in the mapping in the array pMan->vMapping.
- The nodes are stored in the random order.]
+ Description [Collects the nodes used in the mapping in array pMan->vMapping.
+ Nodes are collected in reverse topological order to facilitate the
+ computation of required times.]
SideEffects []
@@ -411,8 +412,9 @@ float Map_CutRefDeref( Map_Cut_t * pCut, int fPhase, int fReference )
***********************************************************************/
void Map_MappingSetRefs( Map_Man_t * pMan )
{
- Map_Node_t * pNode;
- int i, fPhase;
+ Map_Node_t * pNode, ** ppStore;
+ int i, fPhase, LevelMax;
+
// clean all references
for ( i = 0; i < pMan->vNodesAll->nSize; i++ )
{
@@ -421,18 +423,32 @@ void Map_MappingSetRefs( Map_Man_t * pMan )
pNode->nRefAct[1] = 0;
pNode->nRefAct[2] = 0;
}
+
+ // find the largest level of a node
+ LevelMax = 0;
+ for ( i = 0; i < pMan->nOutputs; i++ )
+ if ( LevelMax < (int)Map_Regular(pMan->pOutputs[i])->Level )
+ LevelMax = Map_Regular(pMan->pOutputs[i])->Level;
+
+ // allocate place to store the nodes
+ ppStore = ALLOC( Map_Node_t *, LevelMax + 1 );
+ memset( ppStore, 0, sizeof(Map_Node_t *) * (LevelMax + 1) );
+
// visit nodes reachable from POs in the DFS order through the best cuts
- pMan->vMapping->nSize = 0;
for ( i = 0; i < pMan->nOutputs; i++ )
{
pNode = pMan->pOutputs[i];
fPhase = !Map_IsComplement(pNode);
if ( !Map_NodeIsConst(pNode) )
- Map_MappingSetRefs_rec( pMan, pNode );
- // reference count the PO node
-// Map_Regular(pNode)->nRefAct[fPhase]++;
-// Map_Regular(pNode)->nRefAct[2]++;
+ Map_MappingSetRefs_rec( pMan, pNode, ppStore );
}
+
+ // reconnect the nodes in reverse topological order
+ pMan->vMapping->nSize = 0;
+ for ( i = LevelMax; i >= 0; i-- )
+ for ( pNode = ppStore[i]; pNode; pNode = (Map_Node_t *)pNode->pData0 )
+ Map_NodeVecPush( pMan->vMapping, pNode );
+ free( ppStore );
}
/**Function*************************************************************
@@ -446,7 +462,7 @@ void Map_MappingSetRefs( Map_Man_t * pMan )
SeeAlso []
***********************************************************************/
-void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode )
+void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode, Map_Node_t ** ppStore )
{
Map_Cut_t * pCut;
Map_Node_t * pNodeR;
@@ -459,7 +475,8 @@ void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode )
// add the node to the list of all visited nodes
if ( pNodeR->nRefAct[2]++ == 0 )
- Map_NodeVecPush( pMan->vMapping, pNodeR );
+// Map_NodeVecPush( pMan->vMapping, pNodeR );
+ pNodeR->pData0 = (char *)ppStore[pNodeR->Level], ppStore[pNodeR->Level] = pNodeR;
// quit if the node was already visited in this phase
if ( pNodeR->nRefAct[fPhase]++ )
@@ -482,7 +499,7 @@ void Map_MappingSetRefs_rec( Map_Man_t * pMan, Map_Node_t * pNode )
for ( i = 0; i < pCut->nLeaves; i++ )
{
fInvPin = ((uPhase & (1 << i)) > 0);
- Map_MappingSetRefs_rec( pMan, Map_NotCond(pCut->ppLeaves[i], fInvPin) );
+ Map_MappingSetRefs_rec( pMan, Map_NotCond(pCut->ppLeaves[i], fInvPin), ppStore );
}
}
diff --git a/src/map/mapper/mapperTime.c b/src/map/mapper/mapperTime.c
index 0ff88b0e..f1cafae7 100644
--- a/src/map/mapper/mapperTime.c
+++ b/src/map/mapper/mapperTime.c
@@ -252,7 +252,9 @@ void Map_TimeComputeRequired( Map_Man_t * p, float fRequired )
// sorts the nodes in the decreasing order of levels
// this puts the nodes in reverse topological order
- Map_MappingSortByLevel( p, p->vMapping );
+// Map_MappingSortByLevel( p, p->vMapping );
+ // the array is already sorted by construction in Map_MappingSetRefs()
+
Map_TimePropagateRequired( p, p->vMapping );
}
diff --git a/src/map/mapper/mapperTruth.c b/src/map/mapper/mapperTruth.c
index 97e64920..54fc0391 100644
--- a/src/map/mapper/mapperTruth.c
+++ b/src/map/mapper/mapperTruth.c
@@ -23,7 +23,7 @@
////////////////////////////////////////////////////////////////////////
static void Map_TruthsCut( Map_Man_t * pMan, Map_Cut_t * pCut );
-static void Map_TruthsCutOne( Map_Man_t * p, Map_Cut_t * pCut, unsigned uTruth[] );
+extern void Map_TruthsCutOne( Map_Man_t * p, Map_Cut_t * pCut, unsigned uTruth[] );
static void Map_CutsCollect_rec( Map_Cut_t * pCut, Map_NodeVec_t * vVisited );
////////////////////////////////////////////////////////////////////////
@@ -90,18 +90,30 @@ void Map_MappingTruths( Map_Man_t * pMan )
***********************************************************************/
void Map_TruthsCut( Map_Man_t * p, Map_Cut_t * pCut )
{
- unsigned uTruth[2], uCanon[2];
// unsigned uCanon1, uCanon2;
+ unsigned uTruth[2], uCanon[2];
unsigned char uPhases[16];
+ int fUseFast = 1;
// generally speaking, 1-input cut can be matched into a wire!
if ( pCut->nLeaves == 1 )
return;
+/*
+ if ( p->nVarsMax == 5 )
+ {
+ uTruth[0] = pCut->uTruth;
+ uTruth[1] = pCut->uTruth;
+ }
+ else
+*/
Map_TruthsCutOne( p, pCut, uTruth );
// compute the canonical form for the positive phase
- Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
+ if ( fUseFast )
+ Map_CanonComputeFast( p, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
+ else
+ Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon );
pCut->M[1].uPhase = uPhases[0];
p->nCanons++;
@@ -111,13 +123,15 @@ void Map_TruthsCut( Map_Man_t * p, Map_Cut_t * pCut )
// compute the canonical form for the negative phase
uTruth[0] = ~uTruth[0];
uTruth[1] = ~uTruth[1];
- Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
+ if ( fUseFast )
+ Map_CanonComputeFast( p, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
+ else
+ Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon );
pCut->M[0].uPhase = uPhases[0];
p->nCanons++;
//uCanon2 = uCanon[0] & 0xFFFF;
-
//assert( p->nVarsMax == 4 );
//Rwt_Man4ExploreCount( uCanon1 < uCanon2 ? uCanon1 : uCanon2 );
diff --git a/src/map/mapper/mapperUtils.c b/src/map/mapper/mapperUtils.c
index f8fd1a4c..78885729 100644
--- a/src/map/mapper/mapperUtils.c
+++ b/src/map/mapper/mapperUtils.c
@@ -405,7 +405,7 @@ void Map_MappingPrintOutputArrivals( Map_Man_t * p )
Map_Time_t * pTimes;
Map_Node_t * pNode;
int fPhase, Limit, i;
- int nOutputs;
+ int nOutputs, MaxNameSize;
int * pSorted;
// sort outputs by arrival time
@@ -423,16 +423,22 @@ void Map_MappingPrintOutputArrivals( Map_Man_t * p )
assert( Map_MappingCompareOutputDelay( pSorted, pSorted + nOutputs - 1 ) <= 0 );
s_pMan = NULL;
- // print the latest outputs
+ // determine max size of the node's name
+ MaxNameSize = 0;
Limit = (nOutputs > 5)? 5 : nOutputs;
for ( i = 0; i < Limit; i++ )
+ if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) )
+ MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]);
+
+ // print the latest outputs
+ for ( i = 0; i < Limit; i++ )
{
// get the i-th latest output
pNode = Map_Regular(p->pOutputs[pSorted[i]]);
fPhase =!Map_IsComplement(p->pOutputs[pSorted[i]]);
pTimes = pNode->tArrival + fPhase;
// print out the best arrival time
- printf( "Out %20s : ", p->ppOutputNames[pSorted[i]] );
+ printf( "Output %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] );
printf( "Delay = (%5.2f, %5.2f) ", (double)pTimes->Rise, (double)pTimes->Fall );
printf( "%s", fPhase? "POS" : "NEG" );
printf( "\n" );
@@ -1013,136 +1019,6 @@ void Map_MappingReportChoices( Map_Man_t * pMan )
printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices );
}
-/*
-void Map_MappingReportChoices( Map_Man_t * pMan )
-{
- Map_Node_t * pNode, * pTemp;
- int nChoiceNodes, nChoices;
- int i, LevelMax1, LevelMax2;
- int DiffMaxTotal, DiffMinTotal, Min, Max;
- int CounterByMin[300]={0}, CounterByMax[300]={0};
-
- // report the number of levels
- LevelMax1 = Map_MappingGetMaxLevel( pMan );
- pMan->nTravIds++;
- for ( i = 0; i < pMan->nOutputs; i++ )
-// Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 0 );
- Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 );
- LevelMax2 = Map_MappingGetMaxLevel( pMan );
-
- // report statistics about choices
- nChoiceNodes = nChoices = 0;
- DiffMaxTotal = DiffMinTotal = 0;
- for ( i = 0; i < pMan->vAnds->nSize; i++ )
- {
- pNode = pMan->vAnds->pArray[i];
- if ( pNode->pRepr == NULL && pNode->pNextE != NULL )
- { // this is a choice node = the primary node that has equivalent nodes
- nChoiceNodes++;
- for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE )
- nChoices++;
- // call to compare the levels
- Map_MappingGetChoiceLevels( pMan, pNode, pNode->pNextE, &Min, &Max );
- assert( Min < (int)pNode->Level );
- assert( Max < (int)pNode->Level );
- DiffMinTotal += pNode->Level - Max;
- DiffMaxTotal += pNode->Level - Min;
-
- CounterByMin[pNode->Level - Max]++;
- CounterByMax[pNode->Level - Min]++;
-
- }
- }
- printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 );
- printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices );
- printf( "Choice depth: Minimum = %4.2f. Maximum = %4.2f.\n",
- ((float)DiffMinTotal)/nChoiceNodes, ((float)DiffMaxTotal)/nChoiceNodes );
-
- {
- FILE * pTable;
- pTable = fopen( "statsc.txt", "a+" );
- fprintf( pTable, "%6d ", pMan->vAnds->nSize );
- fprintf( pTable, "%5d ", LevelMax2 );
- fprintf( pTable, "%5d ", nChoiceNodes );
- fprintf( pTable, "%5d ", nChoices );
- fprintf( pTable, "%5.2f ", ((float)DiffMinTotal)/nChoiceNodes );
- fprintf( pTable, "%5.2f ", ((float)DiffMaxTotal)/nChoiceNodes );
-// fprintf( pTable, "%4.2f\n", (float)(Time)/(float)(CLOCKS_PER_SEC) );
- fprintf( pTable, "\n" );
- fclose( pTable );
- }
-
-
- printf( "Distribution by min/max levels:\n" );
- for ( i = 0; i < LevelMax2; i++ )
- printf( "%3d : %5d %5d\n", i, CounterByMin[i], CounterByMax[i] );
- printf( "\n" );
-}
-*/
-
-/*
-void Map_MappingReportChoices( Map_Man_t * pMan )
-{
- Map_Node_t * pNode, * pTemp;
- int nChoiceNodes, nChoices;
- int i, LevelMax1, LevelMax2;
- int CounterByVol[1000]={0};
- float VolumeAve, Volume;
-
- // report the number of levels
- LevelMax1 = Map_MappingGetMaxLevel( pMan );
- pMan->nTravIds++;
- for ( i = 0; i < pMan->nOutputs; i++ )
- Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 0 );
-// Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 );
- LevelMax2 = Map_MappingGetMaxLevel( pMan );
-
- // report statistics about choices
- nChoiceNodes = nChoices = 0;
- VolumeAve = 0.0;
- for ( i = 0; i < pMan->vAnds->nSize; i++ )
- {
- pNode = pMan->vAnds->pArray[i];
- if ( pNode->pRepr == NULL && pNode->pNextE != NULL )
- { // this is a choice node = the primary node that has equivalent nodes
- nChoiceNodes++;
- for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE )
- nChoices++;
- Volume = Map_MappingGetChoiceVolumes( pMan, pNode, pNode->pNextE );
- VolumeAve += Volume;
- assert( Volume < 1000 );
- CounterByVol[(int)Volume]++;
- }
- }
- printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 );
- printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices );
- printf( "Average volume = %5.4f.\n", VolumeAve/nChoiceNodes );
-*/
-/*
- {
- FILE * pTable;
- pTable = fopen( "statsv.txt", "a+" );
- fprintf( pTable, "%6d ", Map_MappingCountUsedNodes(pMan,1) );
- fprintf( pTable, "%6d ", Map_MappingCountUsedNodes(pMan,0) );
- fprintf( pTable, "%5d ", LevelMax1 );
- fprintf( pTable, " " );
- fprintf( pTable, "%5d ", nChoiceNodes );
- fprintf( pTable, "%5d ", nChoices );
- fprintf( pTable, " " );
- fprintf( pTable, "%5.4f ", VolumeAve/nChoiceNodes );
- fprintf( pTable, "\n" );
- fclose( pTable );
- }
- printf( "Distribution by volume:\n" );
- for ( i = 0; i < 1000; i++ )
- if ( CounterByVol[i] > 0 )
- printf( "%3d : %5d\n", i, CounterByVol[i] );
- printf( "\n" );
-*/
-/*
-}
-*/
-
/**Function*************************************************************
Synopsis [Computes the maximum and minimum levels of the choice nodes.]
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-15 05:47:36 +0000