diff options
Diffstat (limited to 'src/aig/nwk/nwkMerge.c')
| -rw-r--r-- | src/aig/nwk/nwkMerge.c | 1044 |
1 files changed, 0 insertions, 1044 deletions
diff --git a/src/aig/nwk/nwkMerge.c b/src/aig/nwk/nwkMerge.c deleted file mode 100644 index 9a4f2f8c..00000000 --- a/src/aig/nwk/nwkMerge.c +++ /dev/null @@ -1,1044 +0,0 @@ -/**CFile**************************************************************** - - FileName [nwkMerge.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Netlist representation.] - - Synopsis [LUT merging algorithm.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: nwkMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "nwk.h" -#include "nwkMerge.h" - -ABC_NAMESPACE_IMPL_START - - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Allocates the graph.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Nwk_Grf_t * Nwk_ManGraphAlloc( int nVertsMax ) -{ - Nwk_Grf_t * p; - p = ABC_ALLOC( Nwk_Grf_t, 1 ); - memset( p, 0, sizeof(Nwk_Grf_t) ); - p->nVertsMax = nVertsMax; - p->nEdgeHash = Aig_PrimeCudd( 3 * nVertsMax ); - p->pEdgeHash = ABC_CALLOC( Nwk_Edg_t *, p->nEdgeHash ); - p->pMemEdges = Aig_MmFixedStart( sizeof(Nwk_Edg_t), p->nEdgeHash ); - p->vPairs = Vec_IntAlloc( 1000 ); - return p; -} - -/**Function************************************************************* - - Synopsis [Deallocates the graph.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManGraphFree( Nwk_Grf_t * p ) -{ - if ( p->vPairs ) Vec_IntFree( p->vPairs ); - if ( p->pMemEdges ) Aig_MmFixedStop( p->pMemEdges, 0 ); - if ( p->pMemVerts ) Aig_MmFlexStop( p->pMemVerts, 0 ); - ABC_FREE( p->pVerts ); - ABC_FREE( p->pEdgeHash ); - ABC_FREE( p->pMapLut2Id ); - ABC_FREE( p->pMapId2Lut ); - ABC_FREE( p ); -} - -/**Function************************************************************* - - Synopsis [Prepares the graph for solving the problem.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManGraphReportMemoryUsage( Nwk_Grf_t * p ) -{ - p->nMemBytes1 = - sizeof(Nwk_Grf_t) + - sizeof(void *) * p->nEdgeHash + - sizeof(int) * (p->nObjs + p->nVertsMax) + - sizeof(Nwk_Edg_t) * p->nEdges; - p->nMemBytes2 = - sizeof(Nwk_Vrt_t) * p->nVerts + - sizeof(int) * 2 * p->nEdges; - printf( "Memory usage stats: Preprocessing = %.2f Mb. Solving = %.2f Mb.\n", - 1.0 * p->nMemBytes1 / (1<<20), 1.0 * p->nMemBytes2 / (1<<20) ); -} - - -/**Function************************************************************* - - Synopsis [Finds or adds the edge to the graph.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManGraphHashEdge( Nwk_Grf_t * p, int iLut1, int iLut2 ) -{ - Nwk_Edg_t * pEntry; - unsigned Key; - if ( iLut1 == iLut2 ) - return; - if ( iLut1 > iLut2 ) - { - Key = iLut1; - iLut1 = iLut2; - iLut2 = Key; - } - assert( iLut1 < iLut2 ); - if ( p->nObjs < iLut2 ) - p->nObjs = iLut2; - Key = (unsigned)(741457 * iLut1 + 4256249 * iLut2) % p->nEdgeHash; - for ( pEntry = p->pEdgeHash[Key]; pEntry; pEntry = pEntry->pNext ) - if ( pEntry->iNode1 == iLut1 && pEntry->iNode2 == iLut2 ) - return; - pEntry = (Nwk_Edg_t *)Aig_MmFixedEntryFetch( p->pMemEdges ); - pEntry->iNode1 = iLut1; - pEntry->iNode2 = iLut2; - pEntry->pNext = p->pEdgeHash[Key]; - p->pEdgeHash[Key] = pEntry; - p->nEdges++; -} - -/**Function************************************************************* - - Synopsis [Adds one entry to the list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline void Nwk_ManGraphListAdd( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex ) -{ - if ( *pList ) - { - Nwk_Vrt_t * pHead; - pHead = p->pVerts[*pList]; - pVertex->iPrev = 0; - pVertex->iNext = pHead->Id; - pHead->iPrev = pVertex->Id; - } - *pList = pVertex->Id; -} - -/**Function************************************************************* - - Synopsis [Deletes one entry from the list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline void Nwk_ManGraphListDelete( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex ) -{ - assert( *pList ); - if ( pVertex->iPrev ) - { -// assert( p->pVerts[pVertex->iPrev]->iNext == pVertex->Id ); - p->pVerts[pVertex->iPrev]->iNext = pVertex->iNext; - } - if ( pVertex->iNext ) - { -// assert( p->pVerts[pVertex->iNext]->iPrev == pVertex->Id ); - p->pVerts[pVertex->iNext]->iPrev = pVertex->iPrev; - } - if ( *pList == pVertex->Id ) - *pList = pVertex->iNext; - pVertex->iPrev = pVertex->iNext = 0; -} - -/**Function************************************************************* - - Synopsis [Inserts the edge into one of the linked lists.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline void Nwk_ManGraphListInsert( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex ) -{ - Nwk_Vrt_t * pNext; - assert( pVertex->nEdges > 0 ); - - if ( pVertex->nEdges == 1 ) - { - pNext = p->pVerts[ pVertex->pEdges[0] ]; - if ( pNext->nEdges >= NWK_MAX_LIST ) - Nwk_ManGraphListAdd( p, p->pLists1 + NWK_MAX_LIST, pVertex ); - else - Nwk_ManGraphListAdd( p, p->pLists1 + pNext->nEdges, pVertex ); - } - else - { - if ( pVertex->nEdges >= NWK_MAX_LIST ) - Nwk_ManGraphListAdd( p, p->pLists2 + NWK_MAX_LIST, pVertex ); - else - Nwk_ManGraphListAdd( p, p->pLists2 + pVertex->nEdges, pVertex ); - } -} - -/**Function************************************************************* - - Synopsis [Extracts the edge from one of the linked lists.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline void Nwk_ManGraphListExtract( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex ) -{ - Nwk_Vrt_t * pNext; - assert( pVertex->nEdges > 0 ); - - if ( pVertex->nEdges == 1 ) - { - pNext = p->pVerts[ pVertex->pEdges[0] ]; - if ( pNext->nEdges >= NWK_MAX_LIST ) - Nwk_ManGraphListDelete( p, p->pLists1 + NWK_MAX_LIST, pVertex ); - else - Nwk_ManGraphListDelete( p, p->pLists1 + pNext->nEdges, pVertex ); - } - else - { - if ( pVertex->nEdges >= NWK_MAX_LIST ) - Nwk_ManGraphListDelete( p, p->pLists2 + NWK_MAX_LIST, pVertex ); - else - Nwk_ManGraphListDelete( p, p->pLists2 + pVertex->nEdges, pVertex ); - } -} - -/**Function************************************************************* - - Synopsis [Prepares the graph for solving the problem.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManGraphPrepare( Nwk_Grf_t * p ) -{ - Nwk_Edg_t * pEntry; - Nwk_Vrt_t * pVertex; - int * pnEdges, nBytes, i; - // allocate memory for the present objects - p->pMapLut2Id = ABC_ALLOC( int, p->nObjs+1 ); - p->pMapId2Lut = ABC_ALLOC( int, p->nVertsMax+1 ); - memset( p->pMapLut2Id, 0xff, sizeof(int) * (p->nObjs+1) ); - memset( p->pMapId2Lut, 0xff, sizeof(int) * (p->nVertsMax+1) ); - // mark present objects - Nwk_GraphForEachEdge( p, pEntry, i ) - { - assert( pEntry->iNode1 <= p->nObjs ); - assert( pEntry->iNode2 <= p->nObjs ); - p->pMapLut2Id[ pEntry->iNode1 ] = 0; - p->pMapLut2Id[ pEntry->iNode2 ] = 0; - } - // map objects - p->nVerts = 0; - for ( i = 0; i <= p->nObjs; i++ ) - { - if ( p->pMapLut2Id[i] == 0 ) - { - p->pMapLut2Id[i] = ++p->nVerts; - p->pMapId2Lut[p->nVerts] = i; - } - } - // count the edges and mark present objects - pnEdges = ABC_CALLOC( int, p->nVerts+1 ); - Nwk_GraphForEachEdge( p, pEntry, i ) - { - // translate into vertices - assert( pEntry->iNode1 <= p->nObjs ); - assert( pEntry->iNode2 <= p->nObjs ); - pEntry->iNode1 = p->pMapLut2Id[pEntry->iNode1]; - pEntry->iNode2 = p->pMapLut2Id[pEntry->iNode2]; - // count the edges - assert( pEntry->iNode1 <= p->nVerts ); - assert( pEntry->iNode2 <= p->nVerts ); - pnEdges[pEntry->iNode1]++; - pnEdges[pEntry->iNode2]++; - } - // allocate the real graph - p->pMemVerts = Aig_MmFlexStart(); - p->pVerts = ABC_ALLOC( Nwk_Vrt_t *, p->nVerts + 1 ); - p->pVerts[0] = NULL; - for ( i = 1; i <= p->nVerts; i++ ) - { - assert( pnEdges[i] > 0 ); - nBytes = sizeof(Nwk_Vrt_t) + sizeof(int) * pnEdges[i]; - p->pVerts[i] = (Nwk_Vrt_t *)Aig_MmFlexEntryFetch( p->pMemVerts, nBytes ); - memset( p->pVerts[i], 0, nBytes ); - p->pVerts[i]->Id = i; - } - // add edges to the real graph - Nwk_GraphForEachEdge( p, pEntry, i ) - { - pVertex = p->pVerts[pEntry->iNode1]; - pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode2; - pVertex = p->pVerts[pEntry->iNode2]; - pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode1; - } - // put vertices into the data structure - for ( i = 1; i <= p->nVerts; i++ ) - { - assert( p->pVerts[i]->nEdges == pnEdges[i] ); - Nwk_ManGraphListInsert( p, p->pVerts[i] ); - } - // clean up - Aig_MmFixedStop( p->pMemEdges, 0 ); p->pMemEdges = NULL; - ABC_FREE( p->pEdgeHash ); -// p->nEdgeHash = 0; - ABC_FREE( pnEdges ); -} - -/**Function************************************************************* - - Synopsis [Sort pairs by the first vertex in the topological order.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManGraphSortPairs( Nwk_Grf_t * p ) -{ - int nSize = Vec_IntSize(p->vPairs); - int * pIdToPair, i; - // allocate storage - pIdToPair = ABC_ALLOC( int, p->nObjs+1 ); - for ( i = 0; i <= p->nObjs; i++ ) - pIdToPair[i] = -1; - // create mapping - for ( i = 0; i < p->vPairs->nSize; i += 2 ) - { - assert( pIdToPair[ p->vPairs->pArray[i] ] == -1 ); - pIdToPair[ p->vPairs->pArray[i] ] = p->vPairs->pArray[i+1]; - } - // recreate pairs - Vec_IntClear( p->vPairs ); - for ( i = 0; i <= p->nObjs; i++ ) - if ( pIdToPair[i] >= 0 ) - { - assert( i < pIdToPair[i] ); - Vec_IntPush( p->vPairs, i ); - Vec_IntPush( p->vPairs, pIdToPair[i] ); - } - assert( nSize == Vec_IntSize(p->vPairs) ); - ABC_FREE( pIdToPair ); -} - - -/**Function************************************************************* - - Synopsis [Updates the problem after pulling out one edge.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManGraphCheckLists( Nwk_Grf_t * p ) -{ - Nwk_Vrt_t * pVertex, * pNext; - int i, j; - assert( p->pLists1[0] == 0 ); - for ( i = 1; i <= NWK_MAX_LIST; i++ ) - if ( p->pLists1[i] ) - { - pVertex = p->pVerts[ p->pLists1[i] ]; - assert( pVertex->nEdges == 1 ); - pNext = p->pVerts[ pVertex->pEdges[0] ]; - assert( pNext->nEdges == i || pNext->nEdges > NWK_MAX_LIST ); - } - // find the next vertext to extract - assert( p->pLists2[0] == 0 ); - assert( p->pLists2[1] == 0 ); - for ( j = 2; j <= NWK_MAX_LIST; j++ ) - if ( p->pLists2[j] ) - { - pVertex = p->pVerts[ p->pLists2[j] ]; - assert( pVertex->nEdges == j || pVertex->nEdges > NWK_MAX_LIST ); - } -} - -/**Function************************************************************* - - Synopsis [Extracts the edge from one of the linked lists.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline void Nwk_ManGraphVertexRemoveEdge( Nwk_Vrt_t * pThis, Nwk_Vrt_t * pNext ) -{ - int k; - for ( k = 0; k < pThis->nEdges; k++ ) - if ( pThis->pEdges[k] == pNext->Id ) - break; - assert( k < pThis->nEdges ); - pThis->nEdges--; - for ( ; k < pThis->nEdges; k++ ) - pThis->pEdges[k] = pThis->pEdges[k+1]; -} - -/**Function************************************************************* - - Synopsis [Updates the problem after pulling out one edge.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManGraphUpdate( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex, Nwk_Vrt_t * pNext ) -{ - Nwk_Vrt_t * pChanged, * pOther; - int i, k; -// Nwk_ManGraphCheckLists( p ); - Nwk_ManGraphListExtract( p, pVertex ); - Nwk_ManGraphListExtract( p, pNext ); - // update neihbors of pVertex - Nwk_VertexForEachAdjacent( p, pVertex, pChanged, i ) - { - if ( pChanged == pNext ) - continue; - Nwk_ManGraphListExtract( p, pChanged ); - // move those that use this one - if ( pChanged->nEdges > 1 ) - Nwk_VertexForEachAdjacent( p, pChanged, pOther, k ) - { - if ( pOther == pVertex || pOther->nEdges > 1 ) - continue; - assert( pOther->nEdges == 1 ); - Nwk_ManGraphListExtract( p, pOther ); - pChanged->nEdges--; - Nwk_ManGraphListInsert( p, pOther ); - pChanged->nEdges++; - } - // remove the edge - Nwk_ManGraphVertexRemoveEdge( pChanged, pVertex ); - // add the changed vertex back - if ( pChanged->nEdges > 0 ) - Nwk_ManGraphListInsert( p, pChanged ); - } - // update neihbors of pNext - Nwk_VertexForEachAdjacent( p, pNext, pChanged, i ) - { - if ( pChanged == pVertex ) - continue; - Nwk_ManGraphListExtract( p, pChanged ); - // move those that use this one - if ( pChanged->nEdges > 1 ) - Nwk_VertexForEachAdjacent( p, pChanged, pOther, k ) - { - if ( pOther == pNext || pOther->nEdges > 1 ) - continue; - assert( pOther->nEdges == 1 ); - Nwk_ManGraphListExtract( p, pOther ); - pChanged->nEdges--; - Nwk_ManGraphListInsert( p, pOther ); - pChanged->nEdges++; - } - // remove the edge - Nwk_ManGraphVertexRemoveEdge( pChanged, pNext ); - // add the changed vertex back - if ( pChanged->nEdges > 0 ) - Nwk_ManGraphListInsert( p, pChanged ); - } - // add to the result - if ( pVertex->Id < pNext->Id ) - { - Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] ); - Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] ); - } - else - { - Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] ); - Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] ); - } -// Nwk_ManGraphCheckLists( p ); -} - -/**Function************************************************************* - - Synopsis [Counts the number of entries in the list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Nwk_ManGraphListLength( Nwk_Grf_t * p, int List ) -{ - Nwk_Vrt_t * pThis; - int fVerbose = 0; - int Counter = 0; - Nwk_ListForEachVertex( p, List, pThis ) - { - if ( fVerbose && Counter < 20 ) - printf( "%d ", p->pVerts[pThis->pEdges[0]]->nEdges ); - Counter++; - } - if ( fVerbose ) - printf( "\n" ); - return Counter; -} - -/**Function************************************************************* - - Synopsis [Returns the adjacent vertex with the mininum number of edges.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Nwk_Vrt_t * Nwk_ManGraphListFindMinEdge( Nwk_Grf_t * p, Nwk_Vrt_t * pVert ) -{ - Nwk_Vrt_t * pThis, * pMinCost = NULL; - int k; - Nwk_VertexForEachAdjacent( p, pVert, pThis, k ) - { - if ( pMinCost == NULL || pMinCost->nEdges > pThis->nEdges ) - pMinCost = pThis; - } - return pMinCost; -} - -/**Function************************************************************* - - Synopsis [Finds the best vertext in the list.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Nwk_Vrt_t * Nwk_ManGraphListFindMin( Nwk_Grf_t * p, int List ) -{ - Nwk_Vrt_t * pThis, * pMinCost = NULL; - int k, Counter = 10000, BestCost = 1000000; - Nwk_ListForEachVertex( p, List, pThis ) - { - for ( k = 0; k < pThis->nEdges; k++ ) - { - if ( pMinCost == NULL || BestCost > p->pVerts[pThis->pEdges[k]]->nEdges ) - { - BestCost = p->pVerts[pThis->pEdges[k]]->nEdges; - pMinCost = pThis; - } - } - if ( --Counter == 0 ) - break; - } - return pMinCost; -} - -/**Function************************************************************* - - Synopsis [Solves the problem by extracting one edge at a time.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManGraphSolve( Nwk_Grf_t * p ) -{ - Nwk_Vrt_t * pVertex, * pNext; - int i, j; - Nwk_ManGraphPrepare( p ); - while ( 1 ) - { - // find the next vertex to extract - assert( p->pLists1[0] == 0 ); - for ( i = 1; i <= NWK_MAX_LIST; i++ ) - if ( p->pLists1[i] ) - { -// printf( "%d ", i ); -// printf( "ListA = %2d. Length = %5d.\n", i, Nwk_ManGraphListLength(p,p->pLists1[i]) ); - pVertex = p->pVerts[ p->pLists1[i] ]; - assert( pVertex->nEdges == 1 ); - pNext = p->pVerts[ pVertex->pEdges[0] ]; - Nwk_ManGraphUpdate( p, pVertex, pNext ); - break; - } - if ( i < NWK_MAX_LIST + 1 ) - continue; - // find the next vertex to extract - assert( p->pLists2[0] == 0 ); - assert( p->pLists2[1] == 0 ); - for ( j = 2; j <= NWK_MAX_LIST; j++ ) - if ( p->pLists2[j] ) - { -// printf( "***%d ", j ); -// printf( "ListB = %2d. Length = %5d.\n", j, Nwk_ManGraphListLength(p,p->pLists2[j]) ); - pVertex = Nwk_ManGraphListFindMin( p, p->pLists2[j] ); - assert( pVertex->nEdges == j || j == NWK_MAX_LIST ); - pNext = Nwk_ManGraphListFindMinEdge( p, pVertex ); - Nwk_ManGraphUpdate( p, pVertex, pNext ); - break; - } - if ( j == NWK_MAX_LIST + 1 ) - break; - } - Nwk_ManGraphSortPairs( p ); -} - -/**Function************************************************************* - - Synopsis [Reads graph from file.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Nwk_Grf_t * Nwk_ManLutMergeReadGraph( char * pFileName ) -{ - Nwk_Grf_t * p; - FILE * pFile; - char Buffer[100]; - int nNodes, nEdges, iNode1, iNode2; - pFile = fopen( pFileName, "r" ); - fscanf( pFile, "%s %d", Buffer, &nNodes ); - fscanf( pFile, "%s %d", Buffer, &nEdges ); - p = Nwk_ManGraphAlloc( nNodes ); - while ( fscanf( pFile, "%s %d %d", Buffer, &iNode1, &iNode2 ) == 3 ) - Nwk_ManGraphHashEdge( p, iNode1, iNode2 ); - assert( p->nEdges == nEdges ); - fclose( pFile ); - return p; -} - -/**Function************************************************************* - - Synopsis [Solves the graph coming from file.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Nwk_ManLutMergeGraphTest( char * pFileName ) -{ - int nPairs; - Nwk_Grf_t * p; - int clk = clock(); - p = Nwk_ManLutMergeReadGraph( pFileName ); - ABC_PRT( "Reading", clock() - clk ); - clk = clock(); - Nwk_ManGraphSolve( p ); - printf( "GRAPH: Nodes = %6d. Edges = %6d. Pairs = %6d. ", - p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 ); - ABC_PRT( "Solving", clock() - clk ); - nPairs = Vec_IntSize(p->vPairs)/2; - Nwk_ManGraphReportMemoryUsage( p ); - Nwk_ManGraphFree( p ); - return nPairs; -} - - - - -/**Function************************************************************* - - Synopsis [Marks the fanins of the node with the current trav ID.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManMarkFanins_rec( Nwk_Obj_t * pLut, int nLevMin ) -{ - Nwk_Obj_t * pNext; - int i; - if ( !Nwk_ObjIsNode(pLut) ) - return; - if ( Nwk_ObjIsTravIdCurrent( pLut ) ) - return; - Nwk_ObjSetTravIdCurrent( pLut ); - if ( Nwk_ObjLevel(pLut) < nLevMin ) - return; - Nwk_ObjForEachFanin( pLut, pNext, i ) - Nwk_ManMarkFanins_rec( pNext, nLevMin ); -} - -/**Function************************************************************* - - Synopsis [Marks the fanouts of the node with the current trav ID.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManMarkFanouts_rec( Nwk_Obj_t * pLut, int nLevMax, int nFanMax ) -{ - Nwk_Obj_t * pNext; - int i; - if ( !Nwk_ObjIsNode(pLut) ) - return; - if ( Nwk_ObjIsTravIdCurrent( pLut ) ) - return; - Nwk_ObjSetTravIdCurrent( pLut ); - if ( Nwk_ObjLevel(pLut) > nLevMax ) - return; - if ( Nwk_ObjFanoutNum(pLut) > nFanMax ) - return; - Nwk_ObjForEachFanout( pLut, pNext, i ) - Nwk_ManMarkFanouts_rec( pNext, nLevMax, nFanMax ); -} - -/**Function************************************************************* - - Synopsis [Collects the circle of nodes around the given set.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManCollectCircle( Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, int nFanMax ) -{ - Nwk_Obj_t * pObj, * pNext; - int i, k; - Vec_PtrClear( vNext ); - Vec_PtrForEachEntry( Nwk_Obj_t *, vStart, pObj, i ) - { - Nwk_ObjForEachFanin( pObj, pNext, k ) - { - if ( !Nwk_ObjIsNode(pNext) ) - continue; - if ( Nwk_ObjIsTravIdCurrent( pNext ) ) - continue; - Nwk_ObjSetTravIdCurrent( pNext ); - Vec_PtrPush( vNext, pNext ); - } - Nwk_ObjForEachFanout( pObj, pNext, k ) - { - if ( !Nwk_ObjIsNode(pNext) ) - continue; - if ( Nwk_ObjIsTravIdCurrent( pNext ) ) - continue; - Nwk_ObjSetTravIdCurrent( pNext ); - if ( Nwk_ObjFanoutNum(pNext) > nFanMax ) - continue; - Vec_PtrPush( vNext, pNext ); - } - } -} - -/**Function************************************************************* - - Synopsis [Collects the circle of nodes removes from the given one.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManCollectNonOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars ) -{ - Vec_Ptr_t * vTemp; - Nwk_Obj_t * pObj; - int i, k; - Vec_PtrClear( vCands ); - if ( pPars->nMaxSuppSize - Nwk_ObjFaninNum(pLut) <= 1 ) - return; - - // collect nodes removed by this distance - assert( pPars->nMaxDistance > 0 ); - Vec_PtrClear( vStart ); - Vec_PtrPush( vStart, pLut ); - Nwk_ManIncrementTravId( pLut->pMan ); - Nwk_ObjSetTravIdCurrent( pLut ); - for ( i = 1; i <= pPars->nMaxDistance; i++ ) - { - Nwk_ManCollectCircle( vStart, vNext, pPars->nMaxFanout ); - vTemp = vStart; - vStart = vNext; - vNext = vTemp; - // collect the nodes in vStart - Vec_PtrForEachEntry( Nwk_Obj_t *, vStart, pObj, k ) - Vec_PtrPush( vCands, pObj ); - } - - // mark the TFI/TFO nodes - Nwk_ManIncrementTravId( pLut->pMan ); - if ( pPars->fUseTfiTfo ) - Nwk_ObjSetTravIdCurrent( pLut ); - else - { - Nwk_ObjSetTravIdPrevious( pLut ); - Nwk_ManMarkFanins_rec( pLut, Nwk_ObjLevel(pLut) - pPars->nMaxDistance ); - Nwk_ObjSetTravIdPrevious( pLut ); - Nwk_ManMarkFanouts_rec( pLut, Nwk_ObjLevel(pLut) + pPars->nMaxDistance, pPars->nMaxFanout ); - } - - // collect nodes satisfying the following conditions: - // - they are close enough in terms of distance - // - they are not in the TFI/TFO of the LUT - // - they have no more than the given number of fanins - // - they have no more than the given diff in delay - k = 0; - Vec_PtrForEachEntry( Nwk_Obj_t *, vCands, pObj, i ) - { - if ( Nwk_ObjIsTravIdCurrent(pObj) ) - continue; - if ( Nwk_ObjFaninNum(pLut) + Nwk_ObjFaninNum(pObj) > pPars->nMaxSuppSize ) - continue; - if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff || - Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff ) - continue; - Vec_PtrWriteEntry( vCands, k++, pObj ); - } - Vec_PtrShrink( vCands, k ); -} - - -/**Function************************************************************* - - Synopsis [Count the total number of fanins.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Nwk_ManCountTotalFanins( Nwk_Obj_t * pLut, Nwk_Obj_t * pCand ) -{ - Nwk_Obj_t * pFanin; - int i, nCounter = Nwk_ObjFaninNum(pLut); - Nwk_ObjForEachFanin( pCand, pFanin, i ) - nCounter += !pFanin->MarkC; - return nCounter; -} - -/**Function************************************************************* - - Synopsis [Collects overlapping candidates.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Nwk_ManCollectOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars ) -{ - Nwk_Obj_t * pFanin, * pObj; - int i, k; - // mark fanins of pLut - Nwk_ObjForEachFanin( pLut, pFanin, i ) - pFanin->MarkC = 1; - // collect the matching fanouts of each fanin of the node - Vec_PtrClear( vCands ); - Nwk_ManIncrementTravId( pLut->pMan ); - Nwk_ObjSetTravIdCurrent( pLut ); - Nwk_ObjForEachFanin( pLut, pFanin, i ) - { - if ( !Nwk_ObjIsNode(pFanin) ) - continue; - if ( Nwk_ObjFanoutNum(pFanin) > pPars->nMaxFanout ) - continue; - Nwk_ObjForEachFanout( pFanin, pObj, k ) - { - if ( !Nwk_ObjIsNode(pObj) ) - continue; - if ( Nwk_ObjIsTravIdCurrent( pObj ) ) - continue; - Nwk_ObjSetTravIdCurrent( pObj ); - // check the difference in delay - if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff || - Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff ) - continue; - // check the total number of fanins of the node - if ( Nwk_ManCountTotalFanins(pLut, pObj) > pPars->nMaxSuppSize ) - continue; - Vec_PtrPush( vCands, pObj ); - } - } - // unmark fanins of pLut - Nwk_ObjForEachFanin( pLut, pFanin, i ) - pFanin->MarkC = 0; -} - -/**Function************************************************************* - - Synopsis [Performs LUT merging with parameters.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Nwk_ManLutMerge( Nwk_Man_t * pNtk, void * pParsInit ) -{ - Nwk_LMPars_t * pPars = (Nwk_LMPars_t *)pParsInit; - Nwk_Grf_t * p; - Vec_Int_t * vResult; - Vec_Ptr_t * vStart, * vNext, * vCands1, * vCands2; - Nwk_Obj_t * pLut, * pCand; - int i, k, nVertsMax, nCands, clk = clock(); - // count the number of vertices - nVertsMax = 0; - Nwk_ManForEachNode( pNtk, pLut, i ) - nVertsMax += (int)(Nwk_ObjFaninNum(pLut) <= pPars->nMaxLutSize); - p = Nwk_ManGraphAlloc( nVertsMax ); - // create graph - vStart = Vec_PtrAlloc( 1000 ); - vNext = Vec_PtrAlloc( 1000 ); - vCands1 = Vec_PtrAlloc( 1000 ); - vCands2 = Vec_PtrAlloc( 1000 ); - nCands = 0; - Nwk_ManForEachNode( pNtk, pLut, i ) - { - if ( Nwk_ObjFaninNum(pLut) > pPars->nMaxLutSize ) - continue; - Nwk_ManCollectOverlapCands( pLut, vCands1, pPars ); - if ( pPars->fUseDiffSupp ) - Nwk_ManCollectNonOverlapCands( pLut, vStart, vNext, vCands2, pPars ); - if ( Vec_PtrSize(vCands1) == 0 && Vec_PtrSize(vCands2) == 0 ) - continue; - nCands += Vec_PtrSize(vCands1) + Vec_PtrSize(vCands2); - // save candidates - Vec_PtrForEachEntry( Nwk_Obj_t *, vCands1, pCand, k ) - Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) ); - Vec_PtrForEachEntry( Nwk_Obj_t *, vCands2, pCand, k ) - Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) ); - // print statistics about this node - if ( pPars->fVeryVerbose ) - printf( "Node %6d : Fanins = %d. Fanouts = %3d. Cand1 = %3d. Cand2 = %3d.\n", - Nwk_ObjId(pLut), Nwk_ObjFaninNum(pLut), Nwk_ObjFaninNum(pLut), - Vec_PtrSize(vCands1), Vec_PtrSize(vCands2) ); - } - Vec_PtrFree( vStart ); - Vec_PtrFree( vNext ); - Vec_PtrFree( vCands1 ); - Vec_PtrFree( vCands2 ); - if ( pPars->fVerbose ) - { - printf( "Mergable LUTs = %6d. Total cands = %6d. ", p->nVertsMax, nCands ); - ABC_PRT( "Deriving graph", clock() - clk ); - } - // solve the graph problem - clk = clock(); - Nwk_ManGraphSolve( p ); - if ( pPars->fVerbose ) - { - printf( "GRAPH: Nodes = %6d. Edges = %6d. Pairs = %6d. ", - p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 ); - ABC_PRT( "Solving", clock() - clk ); - Nwk_ManGraphReportMemoryUsage( p ); - } - vResult = p->vPairs; p->vPairs = NULL; -/* - for ( i = 0; i < vResult->nSize; i += 2 ) - printf( "(%d,%d) ", vResult->pArray[i], vResult->pArray[i+1] ); - printf( "\n" ); -*/ - Nwk_ManGraphFree( p ); - return vResult; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - -ABC_NAMESPACE_IMPL_END - |