/**CFile**************************************************************** FileName [mapperUtils.c] PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] Synopsis [Generic technology mapping engine.] Author [MVSIS Group] Affiliation [UC Berkeley] Date [Ver. 2.0. Started - June 1, 2004.] Revision [$Id: mapperUtils.c,v 1.8 2004/11/03 22:41:45 satrajit Exp $] ***********************************************************************/ #include "mapperInt.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// #define MAP_CO_LIST_SIZE 5 static int Map_MappingCountLevels_rec( Map_Node_t * pNode ); static float Map_MappingSetRefsAndArea_rec( Map_Man_t * pMan, Map_Node_t * pNode ); static float Map_MappingSetRefsAndSwitch_rec( Map_Man_t * pMan, Map_Node_t * pNode ); static float Map_MappingSetRefsAndWire_rec( Map_Man_t * pMan, Map_Node_t * pNode ); static void Map_MappingDfsCuts_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes ); static float Map_MappingArea_rec( Map_Man_t * pMan, Map_Node_t * pNode, Map_NodeVec_t * vNodes ); static int Map_MappingCompareOutputDelay( Map_Node_t ** ppNode1, Map_Node_t ** ppNode2 ); static void Map_MappingFindLatest( Map_Man_t * p, int * pNodes, int nNodesMax ); static unsigned Map_MappingExpandTruth_rec( unsigned uTruth, int nVars ); static int Map_MappingCountUsedNodes( Map_Man_t * pMan, int fChoices ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Computes the DFS ordering of the nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingDfs_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes, int fCollectEquiv ) { assert( !Map_IsComplement(pNode) ); if ( pNode->fMark0 ) return; // visit the transitive fanin if ( Map_NodeIsAnd(pNode) ) { Map_MappingDfs_rec( Map_Regular(pNode->p1), vNodes, fCollectEquiv ); Map_MappingDfs_rec( Map_Regular(pNode->p2), vNodes, fCollectEquiv ); } // visit the equivalent nodes if ( fCollectEquiv && pNode->pNextE ) Map_MappingDfs_rec( pNode->pNextE, vNodes, fCollectEquiv ); // make sure the node is not visited through the equivalent nodes assert( pNode->fMark0 == 0 ); // mark the node as visited pNode->fMark0 = 1; // add the node to the list Map_NodeVecPush( vNodes, pNode ); } Map_NodeVec_t * Map_MappingDfs( Map_Man_t * pMan, int fCollectEquiv ) { Map_NodeVec_t * vNodes; int i; // perform the traversal vNodes = Map_NodeVecAlloc( 100 ); for ( i = 0; i < pMan->nOutputs; i++ ) Map_MappingDfs_rec( Map_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv ); for ( i = 0; i < vNodes->nSize; i++ ) vNodes->pArray[i]->fMark0 = 0; // for ( i = 0; i < pMan->nOutputs; i++ ) // Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) ); return vNodes; } /**Function************************************************************* Synopsis [Computes the number of logic levels not counting PIs/POs.] Description [] SideEffects [Note that this procedure will reassign the levels assigned originally by NodeCreate() because it counts the number of levels with choices differently!] SeeAlso [] ***********************************************************************/ int Map_MappingCountLevels( Map_Man_t * pMan ) { int i, LevelsMax, LevelsCur; // perform the traversal LevelsMax = -1; for ( i = 0; i < pMan->nOutputs; i++ ) { LevelsCur = Map_MappingCountLevels_rec( Map_Regular(pMan->pOutputs[i]) ); if ( LevelsMax < LevelsCur ) LevelsMax = LevelsCur; } for ( i = 0; i < pMan->nOutputs; i++ ) Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) ); return LevelsMax; } /**Function************************************************************* Synopsis [Recursively computes the number of logic levels.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_MappingCountLevels_rec( Map_Node_t * pNode ) { int Level1, Level2; assert( !Map_IsComplement(pNode) ); if ( !Map_NodeIsAnd(pNode) ) { pNode->Level = 0; return 0; } if ( pNode->fMark0 ) return pNode->Level; pNode->fMark0 = 1; // visit the transitive fanin Level1 = Map_MappingCountLevels_rec( Map_Regular(pNode->p1) ); Level2 = Map_MappingCountLevels_rec( Map_Regular(pNode->p2) ); // set the number of levels pNode->Level = 1 + ((Level1>Level2)? Level1: Level2); return pNode->Level; } /**Function************************************************************* Synopsis [Unmarks the nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingUnmark( Map_Man_t * pMan ) { int i; for ( i = 0; i < pMan->nOutputs; i++ ) Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) ); } /**Function************************************************************* Synopsis [Recursively unmarks the nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingUnmark_rec( Map_Node_t * pNode ) { assert( !Map_IsComplement(pNode) ); if ( pNode->fMark0 == 0 ) return; pNode->fMark0 = 0; if ( !Map_NodeIsAnd(pNode) ) return; Map_MappingUnmark_rec( Map_Regular(pNode->p1) ); Map_MappingUnmark_rec( Map_Regular(pNode->p2) ); // visit the equivalent nodes if ( pNode->pNextE ) Map_MappingUnmark_rec( pNode->pNextE ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingMark_rec( Map_Node_t * pNode ) { assert( !Map_IsComplement(pNode) ); if ( pNode->fMark0 == 1 ) return; pNode->fMark0 = 1; if ( !Map_NodeIsAnd(pNode) ) return; // visit the transitive fanin of the selected cut Map_MappingMark_rec( Map_Regular(pNode->p1) ); Map_MappingMark_rec( Map_Regular(pNode->p2) ); } /**Function************************************************************* Synopsis [Compares the outputs by their arrival times.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_MappingCompareOutputDelay( Map_Node_t ** ppNode1, Map_Node_t ** ppNode2 ) { Map_Node_t * pNode1 = Map_Regular(*ppNode1); Map_Node_t * pNode2 = Map_Regular(*ppNode2); int fPhase1 = !Map_IsComplement(*ppNode1); int fPhase2 = !Map_IsComplement(*ppNode2); float Arrival1 = pNode1->tArrival[fPhase1].Worst; float Arrival2 = pNode2->tArrival[fPhase2].Worst; if ( Arrival1 < Arrival2 ) return -1; if ( Arrival1 > Arrival2 ) return 1; return 0; } /**Function************************************************************* Synopsis [Finds given number of latest arriving COs.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingFindLatest( Map_Man_t * p, int * pNodes, int nNodesMax ) { int nNodes, i, k, v; assert( p->nOutputs >= nNodesMax ); pNodes[0] = 0; nNodes = 1; for ( i = 1; i < p->nOutputs; i++ ) { for ( k = nNodes - 1; k >= 0; k-- ) if ( Map_MappingCompareOutputDelay( &p->pOutputs[pNodes[k]], &p->pOutputs[i] ) >= 0 ) break; if ( k == nNodesMax - 1 ) continue; if ( nNodes < nNodesMax ) nNodes++; for ( v = nNodes - 1; v > k+1; v-- ) pNodes[v] = pNodes[v-1]; pNodes[k+1] = i; } } /**Function************************************************************* Synopsis [Prints a bunch of latest arriving outputs.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingPrintOutputArrivals( Map_Man_t * p ) { int pSorted[MAP_CO_LIST_SIZE]; Map_Time_t * pTimes; Map_Node_t * pNode; int fPhase, Limit, i; int MaxNameSize; // determine the number of nodes to print Limit = (p->nOutputs > MAP_CO_LIST_SIZE)? MAP_CO_LIST_SIZE : p->nOutputs; // determine the order Map_MappingFindLatest( p, pSorted, Limit ); // determine max size of the node's name MaxNameSize = 0; 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( "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" ); } } /**Function************************************************************* Synopsis [Sets up the truth tables.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingSetupTruthTables( unsigned uTruths[][2] ) { int m, v; // set up the truth tables for ( m = 0; m < 32; m++ ) for ( v = 0; v < 5; v++ ) if ( m & (1 << v) ) uTruths[v][0] |= (1 << m); // make adjustments for the case of 6 variables for ( v = 0; v < 5; v++ ) uTruths[v][1] = uTruths[v][0]; uTruths[5][0] = 0; uTruths[5][1] = MAP_FULL; } /**Function************************************************************* Synopsis [Sets up the truth tables.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingSetupTruthTablesLarge( unsigned uTruths[][32] ) { int m, v; // clean everything for ( m = 0; m < 32; m++ ) for ( v = 0; v < 10; v++ ) uTruths[v][m] = 0; // set up the truth tables for ( m = 0; m < 32; m++ ) for ( v = 0; v < 5; v++ ) if ( m & (1 << v) ) { uTruths[v][0] |= (1 << m); uTruths[v+5][m] = MAP_FULL; } // extend this info for the rest of the first 5 variables for ( m = 0; m < 32; m++ ) for ( v = 0; v < 5; v++ ) uTruths[v][m] = uTruths[v][0]; /* // verify for ( m = 0; m < 1024; m++, printf("\n") ) for ( v = 0; v < 10; v++ ) if ( Map_InfoReadVar( uTruths[v], m ) ) printf( "1" ); else printf( "0" ); */ } /**Function************************************************************* Synopsis [Sets up the mask.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingSetupMask( unsigned uMask[], int nVarsMax ) { if ( nVarsMax == 6 ) uMask[0] = uMask[1] = MAP_FULL; else { uMask[0] = MAP_MASK(1 << nVarsMax); uMask[1] = 0; } } /**Function************************************************************* Synopsis [Verify one useful property.] Description [This procedure verifies one useful property. After the FRAIG construction with choice nodes is over, each primary node should have fanins that are primary nodes. The primary nodes is the one that does not have pNode->pRepr set to point to another node.] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_ManCheckConsistency( Map_Man_t * p ) { Map_Node_t * pNode; Map_NodeVec_t * pVec; int i; pVec = Map_MappingDfs( p, 0 ); for ( i = 0; i < pVec->nSize; i++ ) { pNode = pVec->pArray[i]; if ( Map_NodeIsVar(pNode) ) { if ( pNode->pRepr ) printf( "Primary input %d is a secondary node.\n", pNode->Num ); } else if ( Map_NodeIsConst(pNode) ) { if ( pNode->pRepr ) printf( "Constant 1 %d is a secondary node.\n", pNode->Num ); } else { if ( pNode->pRepr ) printf( "Internal node %d is a secondary node.\n", pNode->Num ); if ( Map_Regular(pNode->p1)->pRepr ) printf( "Internal node %d has first fanin that is a secondary node.\n", pNode->Num ); if ( Map_Regular(pNode->p2)->pRepr ) printf( "Internal node %d has second fanin that is a secondary node.\n", pNode->Num ); } } Map_NodeVecFree( pVec ); return 1; } /**Function************************************************************* Synopsis [Returns 1 if current mapping of the node violates fanout limits.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_MappingNodeIsViolator( Map_Node_t * pNode, Map_Cut_t * pCut, int fPosPol ) { return pNode->nRefAct[fPosPol] > (int)pCut->M[fPosPol].pSuperBest->nFanLimit; } /**Function************************************************************* Synopsis [Computes the total are flow of the network.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ float Map_MappingGetAreaFlow( Map_Man_t * p ) { Map_Node_t * pNode; Map_Cut_t * pCut; float aFlowFlowTotal = 0; int fPosPol, i; for ( i = 0; i < p->nOutputs; i++ ) { pNode = Map_Regular(p->pOutputs[i]); if ( !Map_NodeIsAnd(pNode) ) continue; fPosPol = !Map_IsComplement(p->pOutputs[i]); pCut = pNode->pCutBest[fPosPol]; if ( pCut == NULL ) { fPosPol = !fPosPol; pCut = pNode->pCutBest[fPosPol]; } aFlowFlowTotal += pNode->pCutBest[fPosPol]->M[fPosPol].AreaFlow; } return aFlowFlowTotal; } /**Function************************************************************* Synopsis [Compares the supergates by their level.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_CompareNodesByLevel( Map_Node_t ** ppS1, Map_Node_t ** ppS2 ) { Map_Node_t * pN1 = Map_Regular(*ppS1); Map_Node_t * pN2 = Map_Regular(*ppS2); if ( pN1->Level > pN2->Level ) return -1; if ( pN1->Level < pN2->Level ) return 1; return 0; } /**Function************************************************************* Synopsis [Orders the nodes in the decreasing order of levels.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingSortByLevel( Map_Man_t * pMan, Map_NodeVec_t * vNodes ) { qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Map_Node_t *), (int (*)(const void *, const void *)) Map_CompareNodesByLevel ); // assert( Map_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 ); } /**Function************************************************************* Synopsis [Compares the supergates by their pointer.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_CompareNodesByPointer( Map_Node_t ** ppS1, Map_Node_t ** ppS2 ) { if ( *ppS1 < *ppS2 ) return -1; if ( *ppS1 > *ppS2 ) return 1; return 0; } /**Function************************************************************* Synopsis [Counts how many AIG nodes are mapped in both polarities.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_MappingCountDoubles( Map_Man_t * pMan, Map_NodeVec_t * vNodes ) { Map_Node_t * pNode; int Counter, i; // count the number of equal adjacent nodes Counter = 0; for ( i = 0; i < vNodes->nSize; i++ ) { pNode = vNodes->pArray[i]; if ( !Map_NodeIsAnd(pNode) ) continue; if ( (pNode->nRefAct[0] && pNode->pCutBest[0]) && (pNode->nRefAct[1] && pNode->pCutBest[1]) ) Counter++; } return Counter; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ st__table * Map_CreateTableGate2Super( Map_Man_t * pMan ) { Map_Super_t * pSuper; st__table * tTable; int i, nInputs, v; tTable = st__init_table(strcmp, st__strhash); for ( i = 0; i < pMan->pSuperLib->nSupersAll; i++ ) { pSuper = pMan->pSuperLib->ppSupers[i]; if ( pSuper->nGates == 1 ) { // skip different versions of the same root gate nInputs = Mio_GateReadPinNum(pSuper->pRoot); for ( v = 0; v < nInputs; v++ ) if ( pSuper->pFanins[v]->Num != nInputs - 1 - v ) break; if ( v != nInputs ) continue; // printf( "%s\n", Mio_GateReadName(pSuper->pRoot) ); if ( st__insert( tTable, (char *)pSuper->pRoot, (char *)pSuper ) ) { assert( 0 ); } } } return tTable; } /**Function************************************************************* Synopsis [Get the FRAIG node with phase.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_ManCleanData( Map_Man_t * p ) { int i; for ( i = 0; i < p->vMapObjs->nSize; i++ ) p->vMapObjs->pArray[i]->pData0 = p->vMapObjs->pArray[i]->pData1 = 0; } /**Function************************************************************* Synopsis [Expand the truth table] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingExpandTruth( unsigned uTruth[2], int nVars ) { assert( nVars < 7 ); if ( nVars == 6 ) return; if ( nVars < 5 ) { uTruth[0] &= MAP_MASK( (1<vMapObjs->nSize; i++ ) { // skip primary inputs pNode = p->vMapObjs->pArray[i]; if ( !Map_NodeIsAnd( pNode ) ) continue; // skip a secondary node if ( pNode->pRepr ) continue; // count the switching nodes if ( pNode->nRefAct[0] > 0 ) Map_TimeCutComputeArrival( pNode, pNode->pCutBest[0], 0, MAP_FLOAT_LARGE ); if ( pNode->nRefAct[1] > 0 ) Map_TimeCutComputeArrival( pNode, pNode->pCutBest[1], 1, MAP_FLOAT_LARGE ); } Result = Map_TimeComputeArrivalMax(p); printf( "Max arrival times with fanouts = %10.2f.\n", Result ); return Result; } /**Function************************************************************* Synopsis [Sets up the mask.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_MappingGetMaxLevel( Map_Man_t * pMan ) { int nLevelMax, i; nLevelMax = 0; for ( i = 0; i < pMan->nOutputs; i++ ) nLevelMax = ((unsigned)nLevelMax) > Map_Regular(pMan->pOutputs[i])->Level? nLevelMax : Map_Regular(pMan->pOutputs[i])->Level; return nLevelMax; } /**Function************************************************************* Synopsis [Analyses choice nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_MappingUpdateLevel_rec( Map_Man_t * pMan, Map_Node_t * pNode, int fMaximum ) { Map_Node_t * pTemp; int Level1, Level2, LevelE; assert( !Map_IsComplement(pNode) ); if ( !Map_NodeIsAnd(pNode) ) return pNode->Level; // skip the visited node if ( pNode->TravId == pMan->nTravIds ) return pNode->Level; pNode->TravId = pMan->nTravIds; // compute levels of the children nodes Level1 = Map_MappingUpdateLevel_rec( pMan, Map_Regular(pNode->p1), fMaximum ); Level2 = Map_MappingUpdateLevel_rec( pMan, Map_Regular(pNode->p2), fMaximum ); pNode->Level = 1 + MAP_MAX( Level1, Level2 ); if ( pNode->pNextE ) { LevelE = Map_MappingUpdateLevel_rec( pMan, pNode->pNextE, fMaximum ); if ( fMaximum ) { if ( pNode->Level < (unsigned)LevelE ) pNode->Level = LevelE; } else { if ( pNode->Level > (unsigned)LevelE ) pNode->Level = LevelE; } // set the level of all equivalent nodes to be the same minimum if ( pNode->pRepr == NULL ) // the primary node for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE ) pTemp->Level = pNode->Level; } return pNode->Level; } /**Function************************************************************* Synopsis [Resets the levels of the nodes in the choice graph.] Description [Makes the level of the choice nodes to be equal to the maximum of the level of the nodes in the equivalence class. This way sorting by level leads to the reverse topological order, which is needed for the required time computation.] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingSetChoiceLevels( Map_Man_t * pMan ) { int i; pMan->nTravIds++; for ( i = 0; i < pMan->nOutputs; i++ ) Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 ); } /**Function************************************************************* Synopsis [Reports statistics on choice nodes.] Description [The number of choice nodes is the number of primary nodes, which has pNextE set to a pointer. The number of choices is the number of entries in the equivalent-node lists of the primary nodes.] SideEffects [] SeeAlso [] ***********************************************************************/ void Map_MappingReportChoices( Map_Man_t * pMan ) { Map_Node_t * pNode, * pTemp; int nChoiceNodes, nChoices; int i, LevelMax1, LevelMax2; // 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 ); LevelMax2 = Map_MappingGetMaxLevel( pMan ); // report statistics about choices nChoiceNodes = nChoices = 0; for ( i = 0; i < pMan->vMapObjs->nSize; i++ ) { pNode = pMan->vMapObjs->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++; } } 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 ); } /**Function************************************************************* Synopsis [Computes the maximum and minimum levels of the choice nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Map_MappingCountUsedNodes( Map_Man_t * pMan, int fChoices ) { Map_NodeVec_t * vNodes; int Result; vNodes = Map_MappingDfs( pMan, fChoices ); Result = vNodes->nSize; Map_NodeVecFree( vNodes ); return Result; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END