/**CFile**************************************************************** FileName [aigPart.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [AIG package.] Synopsis [AIG partitioning package.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - April 28, 2007.] Revision [$Id: aigPart.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] ***********************************************************************/ #include "aig.h" #include "misc/tim/tim.h" #include "proof/fra/fra.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// typedef struct Part_Man_t_ Part_Man_t; struct Part_Man_t_ { int nChunkSize; // the size of one chunk of memory (~1 MB) int nStepSize; // the step size in saving memory (~64 bytes) char * pFreeBuf; // the pointer to free memory int nFreeSize; // the size of remaining free memory Vec_Ptr_t * vMemory; // the memory allocated Vec_Ptr_t * vFree; // the vector of free pieces of memory }; typedef struct Part_One_t_ Part_One_t; struct Part_One_t_ { int nRefs; // the number of references int nOuts; // the number of outputs int nOutsAlloc; // the array size int pOuts[0]; // the array of outputs }; static inline int Part_SizeType( int nSize, int nStepSize ) { return nSize / nStepSize + ((nSize % nStepSize) > 0); } static inline char * Part_OneNext( char * pPart ) { return *((char **)pPart); } static inline void Part_OneSetNext( char * pPart, char * pNext ) { *((char **)pPart) = pNext; } //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Start the memory manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Part_Man_t * Part_ManStart( int nChunkSize, int nStepSize ) { Part_Man_t * p; p = ABC_ALLOC( Part_Man_t, 1 ); memset( p, 0, sizeof(Part_Man_t) ); p->nChunkSize = nChunkSize; p->nStepSize = nStepSize; p->vMemory = Vec_PtrAlloc( 1000 ); p->vFree = Vec_PtrAlloc( 1000 ); return p; } /**Function************************************************************* Synopsis [Stops the memory manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Part_ManStop( Part_Man_t * p ) { void * pMemory; int i; Vec_PtrForEachEntry( void *, p->vMemory, pMemory, i ) ABC_FREE( pMemory ); Vec_PtrFree( p->vMemory ); Vec_PtrFree( p->vFree ); ABC_FREE( p ); } /**Function************************************************************* Synopsis [Fetches the memory entry of the given size.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ char * Part_ManFetch( Part_Man_t * p, int nSize ) { int Type, nSizeReal; char * pMemory; assert( nSize > 0 ); Type = Part_SizeType( nSize, p->nStepSize ); Vec_PtrFillExtra( p->vFree, Type + 1, NULL ); if ( (pMemory = (char *)Vec_PtrEntry( p->vFree, Type )) ) { Vec_PtrWriteEntry( p->vFree, Type, Part_OneNext(pMemory) ); return pMemory; } nSizeReal = p->nStepSize * Type; if ( p->nFreeSize < nSizeReal ) { p->pFreeBuf = ABC_ALLOC( char, p->nChunkSize ); p->nFreeSize = p->nChunkSize; Vec_PtrPush( p->vMemory, p->pFreeBuf ); } assert( p->nFreeSize >= nSizeReal ); pMemory = p->pFreeBuf; p->pFreeBuf += nSizeReal; p->nFreeSize -= nSizeReal; return pMemory; } /**Function************************************************************* Synopsis [Recycles the memory entry of the given size.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Part_ManRecycle( Part_Man_t * p, char * pMemory, int nSize ) { int Type; Type = Part_SizeType( nSize, p->nStepSize ); Vec_PtrFillExtra( p->vFree, Type + 1, NULL ); Part_OneSetNext( pMemory, (char *)Vec_PtrEntry(p->vFree, Type) ); Vec_PtrWriteEntry( p->vFree, Type, pMemory ); } /**Function************************************************************* Synopsis [Fetches the memory entry of the given size.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline Part_One_t * Part_ManFetchEntry( Part_Man_t * p, int nWords, int nRefs ) { Part_One_t * pPart; pPart = (Part_One_t *)Part_ManFetch( p, sizeof(Part_One_t) + sizeof(int) * nWords ); pPart->nRefs = nRefs; pPart->nOuts = 0; pPart->nOutsAlloc = nWords; return pPart; } /**Function************************************************************* Synopsis [Recycles the memory entry of the given size.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Part_ManRecycleEntry( Part_Man_t * p, Part_One_t * pEntry ) { assert( pEntry->nOuts <= pEntry->nOutsAlloc ); assert( pEntry->nOuts >= pEntry->nOutsAlloc/2 ); Part_ManRecycle( p, (char *)pEntry, sizeof(Part_One_t) + sizeof(int) * pEntry->nOutsAlloc ); } /**Function************************************************************* Synopsis [Merges two entries.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Part_One_t * Part_ManMergeEntry( Part_Man_t * pMan, Part_One_t * p1, Part_One_t * p2, int nRefs ) { Part_One_t * p = Part_ManFetchEntry( pMan, p1->nOuts + p2->nOuts, nRefs ); int * pBeg1 = p1->pOuts; int * pBeg2 = p2->pOuts; int * pBeg = p->pOuts; int * pEnd1 = p1->pOuts + p1->nOuts; int * pEnd2 = p2->pOuts + p2->nOuts; while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 ) { if ( *pBeg1 == *pBeg2 ) *pBeg++ = *pBeg1++, pBeg2++; else if ( *pBeg1 < *pBeg2 ) *pBeg++ = *pBeg1++; else *pBeg++ = *pBeg2++; } while ( pBeg1 < pEnd1 ) *pBeg++ = *pBeg1++; while ( pBeg2 < pEnd2 ) *pBeg++ = *pBeg2++; p->nOuts = pBeg - p->pOuts; assert( p->nOuts <= p->nOutsAlloc ); assert( p->nOuts >= p1->nOuts ); assert( p->nOuts >= p2->nOuts ); return p; } /**Function************************************************************* Synopsis [Tranfers the entry.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Int_t * Part_ManTransferEntry( Part_One_t * p ) { Vec_Int_t * vSupp; int i; vSupp = Vec_IntAlloc( p->nOuts ); for ( i = 0; i < p->nOuts; i++ ) Vec_IntPush( vSupp, p->pOuts[i] ); return vSupp; } /**Function************************************************************* Synopsis [Computes supports of the POs in the multi-output AIG.] Description [Returns the array of integer arrays containing indices of the primary inputs for each primary output.] SideEffects [Adds the integer PO number at end of each array.] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManSupports( Aig_Man_t * pMan ) { Vec_Ptr_t * vSupports; Vec_Int_t * vSupp; Part_Man_t * p; Part_One_t * pPart0, * pPart1; Aig_Obj_t * pObj; int i, Counter = 0; // set the number of PIs/POs Aig_ManForEachCi( pMan, pObj, i ) pObj->pNext = (Aig_Obj_t *)(long)i; Aig_ManForEachCo( pMan, pObj, i ) pObj->pNext = (Aig_Obj_t *)(long)i; // start the support computation manager p = Part_ManStart( 1 << 20, 1 << 6 ); // consider objects in the topological order vSupports = Vec_PtrAlloc( Aig_ManCoNum(pMan) ); Aig_ManCleanData(pMan); Aig_ManForEachObj( pMan, pObj, i ) { if ( Aig_ObjIsNode(pObj) ) { pPart0 = (Part_One_t *)Aig_ObjFanin0(pObj)->pData; pPart1 = (Part_One_t *)Aig_ObjFanin1(pObj)->pData; pObj->pData = Part_ManMergeEntry( p, pPart0, pPart1, pObj->nRefs ); assert( pPart0->nRefs > 0 ); if ( --pPart0->nRefs == 0 ) Part_ManRecycleEntry( p, pPart0 ); assert( pPart1->nRefs > 0 ); if ( --pPart1->nRefs == 0 ) Part_ManRecycleEntry( p, pPart1 ); if ( ((Part_One_t *)pObj->pData)->nOuts <= 16 ) Counter++; continue; } if ( Aig_ObjIsCo(pObj) ) { pPart0 = (Part_One_t *)Aig_ObjFanin0(pObj)->pData; vSupp = Part_ManTransferEntry(pPart0); Vec_IntPush( vSupp, (int)(long)pObj->pNext ); Vec_PtrPush( vSupports, vSupp ); assert( pPart0->nRefs > 0 ); if ( --pPart0->nRefs == 0 ) Part_ManRecycleEntry( p, pPart0 ); continue; } if ( Aig_ObjIsCi(pObj) ) { if ( pObj->nRefs ) { pPart0 = Part_ManFetchEntry( p, 1, pObj->nRefs ); pPart0->pOuts[ pPart0->nOuts++ ] = (int)(long)pObj->pNext; pObj->pData = pPart0; } continue; } if ( Aig_ObjIsConst1(pObj) ) { if ( pObj->nRefs ) pObj->pData = Part_ManFetchEntry( p, 0, pObj->nRefs ); continue; } assert( 0 ); } //printf( "Memory usage = %d MB.\n", Vec_PtrSize(p->vMemory) * p->nChunkSize / (1<<20) ); Part_ManStop( p ); // sort supports by size Vec_VecSort( (Vec_Vec_t *)vSupports, 1 ); // clear the number of PIs/POs Aig_ManForEachCi( pMan, pObj, i ) pObj->pNext = NULL; Aig_ManForEachCo( pMan, pObj, i ) pObj->pNext = NULL; /* Aig_ManForEachCo( pMan, pObj, i ) printf( "%d ", Vec_IntSize( Vec_VecEntryInt(vSupports, i) ) ); printf( "\n" ); */ // printf( "%d \n", Counter ); return vSupports; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_ManSupportsTest( Aig_Man_t * pMan ) { Vec_Ptr_t * vSupps; vSupps = Aig_ManSupports( pMan ); Vec_VecFree( (Vec_Vec_t *)vSupps ); } /**Function************************************************************* Synopsis [Computes the set of outputs for each input.] Description [Returns the array of integer arrays containing indices of the primary outputsf for each primary input.] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManSupportsInverse( Aig_Man_t * p ) { Vec_Ptr_t * vSupps, * vSuppsInv; Vec_Int_t * vSupp; int i, k, iIn, iOut; // get structural supports for each output vSupps = Aig_ManSupports( p ); // start the inverse supports vSuppsInv = Vec_PtrAlloc( Aig_ManCiNum(p) ); for ( i = 0; i < Aig_ManCiNum(p); i++ ) Vec_PtrPush( vSuppsInv, Vec_IntAlloc(8) ); // transforms the supports into the inverse supports Vec_PtrForEachEntry( Vec_Int_t *, vSupps, vSupp, i ) { iOut = Vec_IntPop( vSupp ); Vec_IntForEachEntry( vSupp, iIn, k ) Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vSuppsInv, iIn), iOut ); } Vec_VecFree( (Vec_Vec_t *)vSupps ); return vSuppsInv; } /**Function************************************************************* Synopsis [Returns the register dependency matrix.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManSupportsRegisters( Aig_Man_t * p ) { Vec_Ptr_t * vSupports, * vMatrix; Vec_Int_t * vSupp; int iOut, iIn, k, m, i; // get structural supports for each output vSupports = Aig_ManSupports( p ); // transforms the supports into the latch dependency matrix vMatrix = Vec_PtrStart( Aig_ManRegNum(p) ); Vec_PtrForEachEntry( Vec_Int_t *, vSupports, vSupp, i ) { // skip true POs iOut = Vec_IntPop( vSupp ); iOut -= Aig_ManCoNum(p) - Aig_ManRegNum(p); if ( iOut < 0 ) { Vec_IntFree( vSupp ); continue; } // remove PIs m = 0; Vec_IntForEachEntry( vSupp, iIn, k ) { iIn -= Aig_ManCiNum(p) - Aig_ManRegNum(p); if ( iIn < 0 ) continue; assert( iIn < Aig_ManRegNum(p) ); Vec_IntWriteEntry( vSupp, m++, iIn ); } Vec_IntShrink( vSupp, m ); // store support in the matrix assert( iOut < Aig_ManRegNum(p) ); Vec_PtrWriteEntry( vMatrix, iOut, vSupp ); } Vec_PtrFree( vSupports ); // check that all supports are used Vec_PtrForEachEntry( Vec_Int_t *, vMatrix, vSupp, i ) assert( vSupp != NULL ); return vMatrix; } /**Function************************************************************* Synopsis [Start char-bases support representation.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ unsigned * Aig_ManSuppCharStart( Vec_Int_t * vOne, int nPis ) { unsigned * pBuffer; int i, Entry; int nWords = Abc_BitWordNum(nPis); pBuffer = ABC_ALLOC( unsigned, nWords ); memset( pBuffer, 0, sizeof(unsigned) * nWords ); Vec_IntForEachEntry( vOne, Entry, i ) { assert( Entry < nPis ); Abc_InfoSetBit( pBuffer, Entry ); } return pBuffer; } /**Function************************************************************* Synopsis [Add to char-bases support representation.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_ManSuppCharAdd( unsigned * pBuffer, Vec_Int_t * vOne, int nPis ) { int i, Entry; Vec_IntForEachEntry( vOne, Entry, i ) { assert( Entry < nPis ); Abc_InfoSetBit( pBuffer, Entry ); } } /**Function************************************************************* Synopsis [Find the common variables using char-bases support representation.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Aig_ManSuppCharCommon( unsigned * pBuffer, Vec_Int_t * vOne ) { int i, Entry, nCommon = 0; Vec_IntForEachEntry( vOne, Entry, i ) nCommon += Abc_InfoHasBit(pBuffer, Entry); return nCommon; } /**Function************************************************************* Synopsis [Find the best partition.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Aig_ManPartitionSmartFindPart( Vec_Ptr_t * vPartSuppsAll, Vec_Ptr_t * vPartsAll, Vec_Ptr_t * vPartSuppsBit, int nSuppSizeLimit, Vec_Int_t * vOne ) { Vec_Int_t * vPartSupp;//, * vPart; int Attract, Repulse, Value, ValueBest; int i, nCommon, iBest; iBest = -1; ValueBest = 0; Vec_PtrForEachEntry( Vec_Int_t *, vPartSuppsAll, vPartSupp, i ) { // vPart = Vec_PtrEntry( vPartsAll, i ); // if ( nSuppSizeLimit > 0 && Vec_IntSize(vPart) >= nSuppSizeLimit ) // continue; // nCommon = Vec_IntTwoCountCommon( vPartSupp, vOne ); nCommon = Aig_ManSuppCharCommon( (unsigned *)Vec_PtrEntry(vPartSuppsBit, i), vOne ); if ( nCommon == 0 ) continue; if ( nCommon == Vec_IntSize(vOne) ) return i; // skip partitions whose size exceeds the limit if ( nSuppSizeLimit > 0 && Vec_IntSize(vPartSupp) >= 2 * nSuppSizeLimit ) continue; Attract = 1000 * nCommon / Vec_IntSize(vOne); if ( Vec_IntSize(vPartSupp) < 100 ) Repulse = 1; else Repulse = 1+Abc_Base2Log(Vec_IntSize(vPartSupp)-100); Value = Attract/Repulse; if ( ValueBest < Value ) { ValueBest = Value; iBest = i; } } if ( ValueBest < 75 ) return -1; return iBest; } /**Function************************************************************* Synopsis [Perform the smart partitioning.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_ManPartitionPrint( Aig_Man_t * p, Vec_Ptr_t * vPartsAll, Vec_Ptr_t * vPartSuppsAll ) { Vec_Int_t * vOne; int i, nOutputs, Counter; Counter = 0; Vec_PtrForEachEntry( Vec_Int_t *, vPartSuppsAll, vOne, i ) { nOutputs = Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vPartsAll, i)); printf( "%d=(%d,%d) ", i, Vec_IntSize(vOne), nOutputs ); Counter += nOutputs; if ( i == Vec_PtrSize(vPartsAll) - 1 ) break; } assert( Counter == Aig_ManCoNum(p) ); // printf( "\nTotal = %d. Outputs = %d.\n", Counter, Aig_ManCoNum(p) ); } /**Function************************************************************* Synopsis [Perform the smart partitioning.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_ManPartitionCompact( Vec_Ptr_t * vPartsAll, Vec_Ptr_t * vPartSuppsAll, int nSuppSizeLimit ) { Vec_Int_t * vOne, * vPart, * vPartSupp, * vTemp; int i, iPart; if ( nSuppSizeLimit == 0 ) nSuppSizeLimit = 200; // pack smaller partitions into larger blocks iPart = 0; vPart = vPartSupp = NULL; Vec_PtrForEachEntry( Vec_Int_t *, vPartSuppsAll, vOne, i ) { if ( Vec_IntSize(vOne) < nSuppSizeLimit ) { if ( vPartSupp == NULL ) { assert( vPart == NULL ); vPartSupp = Vec_IntDup(vOne); vPart = (Vec_Int_t *)Vec_PtrEntry(vPartsAll, i); } else { vPartSupp = Vec_IntTwoMerge( vTemp = vPartSupp, vOne ); Vec_IntFree( vTemp ); vPart = Vec_IntTwoMerge( vTemp = vPart, (Vec_Int_t *)Vec_PtrEntry(vPartsAll, i) ); Vec_IntFree( vTemp ); Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vPartsAll, i) ); } if ( Vec_IntSize(vPartSupp) < nSuppSizeLimit ) continue; } else vPart = (Vec_Int_t *)Vec_PtrEntry(vPartsAll, i); // add the partition Vec_PtrWriteEntry( vPartsAll, iPart, vPart ); vPart = NULL; if ( vPartSupp ) { Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vPartSuppsAll, iPart) ); Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp ); vPartSupp = NULL; } iPart++; } // add the last one if ( vPart ) { Vec_PtrWriteEntry( vPartsAll, iPart, vPart ); vPart = NULL; assert( vPartSupp != NULL ); Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vPartSuppsAll, iPart) ); Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp ); vPartSupp = NULL; iPart++; } Vec_PtrShrink( vPartsAll, iPart ); Vec_PtrShrink( vPartsAll, iPart ); } /**Function************************************************************* Synopsis [Perform the smart partitioning.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManPartitionSmart( Aig_Man_t * p, int nSuppSizeLimit, int fVerbose, Vec_Ptr_t ** pvPartSupps ) { Vec_Ptr_t * vPartSuppsBit; Vec_Ptr_t * vSupports, * vPartsAll, * vPartsAll2, * vPartSuppsAll;//, * vPartPtr; Vec_Int_t * vOne, * vPart, * vPartSupp, * vTemp; int i, iPart, iOut; abctime clk; // compute the supports for all outputs clk = Abc_Clock(); vSupports = Aig_ManSupports( p ); if ( fVerbose ) { ABC_PRT( "Supps", Abc_Clock() - clk ); } // start char-based support representation vPartSuppsBit = Vec_PtrAlloc( 1000 ); // create partitions clk = Abc_Clock(); vPartsAll = Vec_PtrAlloc( 256 ); vPartSuppsAll = Vec_PtrAlloc( 256 ); Vec_PtrForEachEntry( Vec_Int_t *, vSupports, vOne, i ) { // get the output number iOut = Vec_IntPop(vOne); // find closely matching part iPart = Aig_ManPartitionSmartFindPart( vPartSuppsAll, vPartsAll, vPartSuppsBit, nSuppSizeLimit, vOne ); if ( iPart == -1 ) { // create new partition vPart = Vec_IntAlloc( 32 ); Vec_IntPush( vPart, iOut ); // create new partition support vPartSupp = Vec_IntDup( vOne ); // add this partition and its support Vec_PtrPush( vPartsAll, vPart ); Vec_PtrPush( vPartSuppsAll, vPartSupp ); Vec_PtrPush( vPartSuppsBit, Aig_ManSuppCharStart(vOne, Aig_ManCiNum(p)) ); } else { // add output to this partition vPart = (Vec_Int_t *)Vec_PtrEntry( vPartsAll, iPart ); Vec_IntPush( vPart, iOut ); // merge supports vPartSupp = (Vec_Int_t *)Vec_PtrEntry( vPartSuppsAll, iPart ); vPartSupp = Vec_IntTwoMerge( vTemp = vPartSupp, vOne ); Vec_IntFree( vTemp ); // reinsert new support Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp ); Aig_ManSuppCharAdd( (unsigned *)Vec_PtrEntry(vPartSuppsBit, iPart), vOne, Aig_ManCiNum(p) ); } } // stop char-based support representation Vec_PtrForEachEntry( Vec_Int_t *, vPartSuppsBit, vTemp, i ) ABC_FREE( vTemp ); Vec_PtrFree( vPartSuppsBit ); //printf( "\n" ); if ( fVerbose ) { ABC_PRT( "Parts", Abc_Clock() - clk ); } clk = Abc_Clock(); // reorder partitions in the decreasing order of support sizes // remember partition number in each partition support Vec_PtrForEachEntry( Vec_Int_t *, vPartSuppsAll, vOne, i ) Vec_IntPush( vOne, i ); // sort the supports in the decreasing order Vec_VecSort( (Vec_Vec_t *)vPartSuppsAll, 1 ); // reproduce partitions vPartsAll2 = Vec_PtrAlloc( 256 ); Vec_PtrForEachEntry( Vec_Int_t *, vPartSuppsAll, vOne, i ) Vec_PtrPush( vPartsAll2, Vec_PtrEntry(vPartsAll, Vec_IntPop(vOne)) ); Vec_PtrFree( vPartsAll ); vPartsAll = vPartsAll2; // compact small partitions // Aig_ManPartitionPrint( p, vPartsAll, vPartSuppsAll ); Aig_ManPartitionCompact( vPartsAll, vPartSuppsAll, nSuppSizeLimit ); if ( fVerbose ) // Aig_ManPartitionPrint( p, vPartsAll, vPartSuppsAll ); printf( "Created %d partitions.\n", Vec_PtrSize(vPartsAll) ); if ( fVerbose ) { //ABC_PRT( "Comps", Abc_Clock() - clk ); } // cleanup Vec_VecFree( (Vec_Vec_t *)vSupports ); if ( pvPartSupps == NULL ) Vec_VecFree( (Vec_Vec_t *)vPartSuppsAll ); else *pvPartSupps = vPartSuppsAll; /* // converts from intergers to nodes Vec_PtrForEachEntry( Vec_Int_t *, vPartsAll, vPart, iPart ) { vPartPtr = Vec_PtrAlloc( Vec_IntSize(vPart) ); Vec_IntForEachEntry( vPart, iOut, i ) Vec_PtrPush( vPartPtr, Aig_ManCo(p, iOut) ); Vec_IntFree( vPart ); Vec_PtrWriteEntry( vPartsAll, iPart, vPartPtr ); } */ return vPartsAll; } /**Function************************************************************* Synopsis [Perform the smart partitioning.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManPartitionSmartRegisters( Aig_Man_t * pAig, int nSuppSizeLimit, int fVerbose ) { Vec_Ptr_t * vPartSuppsBit; Vec_Ptr_t * vSupports, * vPartsAll, * vPartsAll2, * vPartSuppsAll; Vec_Int_t * vOne, * vPart, * vPartSupp, * vTemp; int i, iPart, iOut; abctime clk; // add output number to each clk = Abc_Clock(); vSupports = Aig_ManSupportsRegisters( pAig ); assert( Vec_PtrSize(vSupports) == Aig_ManRegNum(pAig) ); Vec_PtrForEachEntry( Vec_Int_t *, vSupports, vOne, i ) Vec_IntPush( vOne, i ); if ( fVerbose ) { ABC_PRT( "Supps", Abc_Clock() - clk ); } // start char-based support representation vPartSuppsBit = Vec_PtrAlloc( 1000 ); // create partitions clk = Abc_Clock(); vPartsAll = Vec_PtrAlloc( 256 ); vPartSuppsAll = Vec_PtrAlloc( 256 ); Vec_PtrForEachEntry( Vec_Int_t *, vSupports, vOne, i ) { // get the output number iOut = Vec_IntPop(vOne); // find closely matching part iPart = Aig_ManPartitionSmartFindPart( vPartSuppsAll, vPartsAll, vPartSuppsBit, nSuppSizeLimit, vOne ); if ( iPart == -1 ) { // create new partition vPart = Vec_IntAlloc( 32 ); Vec_IntPush( vPart, iOut ); // create new partition support vPartSupp = Vec_IntDup( vOne ); // add this partition and its support Vec_PtrPush( vPartsAll, vPart ); Vec_PtrPush( vPartSuppsAll, vPartSupp ); Vec_PtrPush( vPartSuppsBit, Aig_ManSuppCharStart(vOne, Vec_PtrSize(vSupports)) ); } else { // add output to this partition vPart = (Vec_Int_t *)Vec_PtrEntry( vPartsAll, iPart ); Vec_IntPush( vPart, iOut ); // merge supports vPartSupp = (Vec_Int_t *)Vec_PtrEntry( vPartSuppsAll, iPart ); vPartSupp = Vec_IntTwoMerge( vTemp = vPartSupp, vOne ); Vec_IntFree( vTemp ); // reinsert new support Vec_PtrWriteEntry( vPartSuppsAll, iPart, vPartSupp ); Aig_ManSuppCharAdd( (unsigned *)Vec_PtrEntry(vPartSuppsBit, iPart), vOne, Vec_PtrSize(vSupports) ); } } // stop char-based support representation Vec_PtrForEachEntry( Vec_Int_t *, vPartSuppsBit, vTemp, i ) ABC_FREE( vTemp ); Vec_PtrFree( vPartSuppsBit ); //printf( "\n" ); if ( fVerbose ) { ABC_PRT( "Parts", Abc_Clock() - clk ); } clk = Abc_Clock(); // reorder partitions in the decreasing order of support sizes // remember partition number in each partition support Vec_PtrForEachEntry( Vec_Int_t *, vPartSuppsAll, vOne, i ) Vec_IntPush( vOne, i ); // sort the supports in the decreasing order Vec_VecSort( (Vec_Vec_t *)vPartSuppsAll, 1 ); // reproduce partitions vPartsAll2 = Vec_PtrAlloc( 256 ); Vec_PtrForEachEntry( Vec_Int_t *, vPartSuppsAll, vOne, i ) Vec_PtrPush( vPartsAll2, Vec_PtrEntry(vPartsAll, Vec_IntPop(vOne)) ); Vec_PtrFree( vPartsAll ); vPartsAll = vPartsAll2; // compact small partitions // Aig_ManPartitionPrint( p, vPartsAll, vPartSuppsAll ); Aig_ManPartitionCompact( vPartsAll, vPartSuppsAll, nSuppSizeLimit ); if ( fVerbose ) // Aig_ManPartitionPrint( p, vPartsAll, vPartSuppsAll ); printf( "Created %d partitions.\n", Vec_PtrSize(vPartsAll) ); if ( fVerbose ) { //ABC_PRT( "Comps", Abc_Clock() - clk ); } // cleanup Vec_VecFree( (Vec_Vec_t *)vSupports ); // if ( pvPartSupps == NULL ) Vec_VecFree( (Vec_Vec_t *)vPartSuppsAll ); // else // *pvPartSupps = vPartSuppsAll; /* // converts from intergers to nodes Vec_PtrForEachEntry( Vec_Int_t *, vPartsAll, vPart, iPart ) { vPartPtr = Vec_PtrAlloc( Vec_IntSize(vPart) ); Vec_IntForEachEntry( vPart, iOut, i ) Vec_PtrPush( vPartPtr, Aig_ManCo(p, iOut) ); Vec_IntFree( vPart ); Vec_PtrWriteEntry( vPartsAll, iPart, vPartPtr ); } */ return vPartsAll; } /**Function************************************************************* Synopsis [Perform the naive partitioning.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManPartitionNaive( Aig_Man_t * p, int nPartSize ) { Vec_Ptr_t * vParts; Aig_Obj_t * pObj; int nParts, i; nParts = (Aig_ManCoNum(p) / nPartSize) + ((Aig_ManCoNum(p) % nPartSize) > 0); vParts = (Vec_Ptr_t *)Vec_VecStart( nParts ); Aig_ManForEachCo( p, pObj, i ) Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vParts, i / nPartSize), i ); return vParts; } /**Function************************************************************* Synopsis [Adds internal nodes in the topological order.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Aig_Obj_t * Aig_ManDupPart_rec( Aig_Man_t * pNew, Aig_Man_t * pOld, Aig_Obj_t * pObj, Vec_Int_t * vSuppMap ) { assert( !Aig_IsComplement(pObj) ); if ( Aig_ObjIsTravIdCurrent(pOld, pObj) ) return (Aig_Obj_t *)pObj->pData; Aig_ObjSetTravIdCurrent(pOld, pObj); if ( Aig_ObjIsCi(pObj) ) { assert( Vec_IntSize(vSuppMap) == Aig_ManCiNum(pNew) ); Vec_IntPush( vSuppMap, (int)(long)pObj->pNext ); return (Aig_Obj_t *)(pObj->pData = Aig_ObjCreateCi(pNew)); } assert( Aig_ObjIsNode(pObj) ); Aig_ManDupPart_rec( pNew, pOld, Aig_ObjFanin0(pObj), vSuppMap ); Aig_ManDupPart_rec( pNew, pOld, Aig_ObjFanin1(pObj), vSuppMap ); return (Aig_Obj_t *)(pObj->pData = Aig_And( pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) )); } /**Function************************************************************* Synopsis [Adds internal nodes in the topological order.] Description [Returns the array of new outputs.] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManDupPart( Aig_Man_t * pNew, Aig_Man_t * pOld, Vec_Int_t * vPart, Vec_Int_t * vSuppMap, int fInverse ) { Vec_Ptr_t * vOutsTotal; Aig_Obj_t * pObj; int Entry, i; // create the PIs Aig_ManIncrementTravId( pOld ); Aig_ManConst1(pOld)->pData = Aig_ManConst1(pNew); Aig_ObjSetTravIdCurrent( pOld, Aig_ManConst1(pOld) ); if ( !fInverse ) { Vec_IntForEachEntry( vSuppMap, Entry, i ) { pObj = Aig_ManCi( pOld, Entry ); pObj->pData = Aig_ManCi( pNew, i ); Aig_ObjSetTravIdCurrent( pOld, pObj ); } } else { Vec_IntForEachEntry( vSuppMap, Entry, i ) { pObj = Aig_ManCi( pOld, i ); pObj->pData = Aig_ManCi( pNew, Entry ); Aig_ObjSetTravIdCurrent( pOld, pObj ); } vSuppMap = NULL; // should not be useful } // create the internal nodes vOutsTotal = Vec_PtrAlloc( Vec_IntSize(vPart) ); if ( !fInverse ) { Vec_IntForEachEntry( vPart, Entry, i ) { pObj = Aig_ManCo( pOld, Entry ); Aig_ManDupPart_rec( pNew, pOld, Aig_ObjFanin0(pObj), vSuppMap ); Vec_PtrPush( vOutsTotal, Aig_ObjChild0Copy(pObj) ); } } else { Aig_ManForEachObj( pOld, pObj, i ) { if ( Aig_ObjIsCo(pObj) ) { Aig_ManDupPart_rec( pNew, pOld, Aig_ObjFanin0(pObj), vSuppMap ); Vec_PtrPush( vOutsTotal, Aig_ObjChild0Copy(pObj) ); } else if ( Aig_ObjIsNode(pObj) && pObj->nRefs == 0 ) Aig_ManDupPart_rec( pNew, pOld, pObj, vSuppMap ); } } return vOutsTotal; } /**Function************************************************************* Synopsis [Adds internal nodes in the topological order.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_ManDupPartAll_rec( Aig_Man_t * pNew, Aig_Man_t * pOld, Aig_Obj_t * pObj ) { Aig_Obj_t * pObjNew; assert( !Aig_IsComplement(pObj) ); if ( Aig_ObjIsTravIdCurrent(pOld, pObj) ) return; Aig_ObjSetTravIdCurrent(pOld, pObj); if ( Aig_ObjIsCi(pObj) ) pObjNew = Aig_ObjCreateCi(pNew); else if ( Aig_ObjIsCo(pObj) ) { Aig_ManDupPartAll_rec( pNew, pOld, Aig_ObjFanin0(pObj) ); pObjNew = Aig_ObjCreateCo( pNew, Aig_ObjChild0Copy(pObj) ); } else { assert( Aig_ObjIsNode(pObj) ); Aig_ManDupPartAll_rec( pNew, pOld, Aig_ObjFanin0(pObj) ); Aig_ManDupPartAll_rec( pNew, pOld, Aig_ObjFanin1(pObj) ); pObjNew = Aig_And( pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) ); } pObj->pData = pObjNew; pObjNew->pData = pObj; } /**Function************************************************************* Synopsis [Adds internal nodes in the topological order.] Description [Returns the array of new outputs.] SideEffects [] SeeAlso [] ***********************************************************************/ Aig_Man_t * Aig_ManDupPartAll( Aig_Man_t * pOld, Vec_Int_t * vPart ) { Aig_Man_t * pNew; Aig_Obj_t * pObj, * pObjNew; int i, Entry; Aig_ManIncrementTravId( pOld ); pNew = Aig_ManStart( 5000 ); // map constant nodes pObj = Aig_ManConst1(pOld); pObjNew = Aig_ManConst1(pNew); pObj->pData = pObjNew; pObjNew->pData = pObj; Aig_ObjSetTravIdCurrent(pOld, pObj); // map all other nodes Vec_IntForEachEntry( vPart, Entry, i ) { pObj = Aig_ManCo( pOld, Entry ); Aig_ManDupPartAll_rec( pNew, pOld, pObj ); } return pNew; } /**Function************************************************************* Synopsis [Collects internal nodes in the DFS order.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_ManSupportNodes_rec( Aig_Man_t * p, Aig_Obj_t * pObj, Vec_Int_t * vSupport ) { if ( Aig_ObjIsTravIdCurrent(p, pObj) ) return; Aig_ObjSetTravIdCurrent(p, pObj); if ( Aig_ObjIsCi(pObj) ) { Vec_IntPush( vSupport, Aig_ObjCioId(pObj) ); return; } Aig_ManSupportNodes_rec( p, Aig_ObjFanin0(pObj), vSupport ); Aig_ManSupportNodes_rec( p, Aig_ObjFanin1(pObj), vSupport ); } /**Function************************************************************* Synopsis [Collects internal nodes and PIs in the DFS order.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManSupportNodes( Aig_Man_t * p, Vec_Ptr_t * vParts ) { Vec_Ptr_t * vPartSupps; Vec_Int_t * vPart, * vSupport; int i, k, iOut; Aig_ManSetCioIds( p ); vPartSupps = Vec_PtrAlloc( Vec_PtrSize(vParts) ); Vec_PtrForEachEntry( Vec_Int_t *, vParts, vPart, i ) { vSupport = Vec_IntAlloc( 100 ); Aig_ManIncrementTravId( p ); Aig_ObjSetTravIdCurrent( p, Aig_ManConst1(p) ); Vec_IntForEachEntry( vPart, iOut, k ) Aig_ManSupportNodes_rec( p, Aig_ObjFanin0(Aig_ManCo(p, iOut)), vSupport ); // Vec_IntSort( vSupport, 0 ); Vec_PtrPush( vPartSupps, vSupport ); } Aig_ManCleanCioIds( p ); return vPartSupps; } /**Function************************************************************* Synopsis [Create partitioned miter of the two AIGs.] Description [Assumes that each output in the second AIG cannot have more supp vars than the same output in the first AIG.] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Ptr_t * Aig_ManMiterPartitioned( Aig_Man_t * p1, Aig_Man_t * p2, int nPartSize, int fSmart ) { Aig_Man_t * pNew; Aig_Obj_t * pMiter; Vec_Ptr_t * vMiters, * vNodes1, * vNodes2; Vec_Ptr_t * vParts, * vPartSupps; Vec_Int_t * vPart, * vPartSupp; int i, k; // partition the first manager if ( fSmart ) vParts = Aig_ManPartitionSmart( p1, nPartSize, 0, &vPartSupps ); else { vParts = Aig_ManPartitionNaive( p1, nPartSize ); vPartSupps = Aig_ManSupportNodes( p1, vParts ); } // derive miters vMiters = Vec_PtrAlloc( Vec_PtrSize(vParts) ); for ( i = 0; i < Vec_PtrSize(vParts); i++ ) { // get partition and its support vPart = (Vec_Int_t *)Vec_PtrEntry( vParts, i ); vPartSupp = (Vec_Int_t *)Vec_PtrEntry( vPartSupps, i ); // create the new miter pNew = Aig_ManStart( 1000 ); // create the PIs for ( k = 0; k < Vec_IntSize(vPartSupp); k++ ) Aig_ObjCreateCi( pNew ); // copy the components vNodes1 = Aig_ManDupPart( pNew, p1, vPart, vPartSupp, 0 ); vNodes2 = Aig_ManDupPart( pNew, p2, vPart, vPartSupp, 0 ); // create the miter pMiter = Aig_MiterTwo( pNew, vNodes1, vNodes2 ); Vec_PtrFree( vNodes1 ); Vec_PtrFree( vNodes2 ); // create the output Aig_ObjCreateCo( pNew, pMiter ); // clean up Aig_ManCleanup( pNew ); Vec_PtrPush( vMiters, pNew ); } Vec_VecFree( (Vec_Vec_t *)vParts ); Vec_VecFree( (Vec_Vec_t *)vPartSupps ); return vMiters; } /**Function************************************************************* Synopsis [Performs partitioned choice computation.] Description [Assumes that each output in the second AIG cannot have more supp vars than the same output in the first AIG.] SideEffects [] SeeAlso [] ***********************************************************************/ Aig_Man_t * Aig_ManChoicePartitioned( Vec_Ptr_t * vAigs, int nPartSize, int nConfMax, int nLevelMax, int fVerbose ) { // extern int Cmd_CommandExecute( void * pAbc, char * sCommand ); // extern void * Abc_FrameGetGlobalFrame(); // extern Aig_Man_t * Fra_FraigChoice( Aig_Man_t * pManAig, int nConfMax, int nLevelMax ); Vec_Ptr_t * vPios; Vec_Ptr_t * vOutsTotal, * vOuts; Aig_Man_t * pAigTotal, * pAigPart, * pAig, * pTemp; Vec_Int_t * vPart, * vPartSupp; Vec_Ptr_t * vParts; Aig_Obj_t * pObj; void ** ppData; int i, k, m, nIdMax; assert( Vec_PtrSize(vAigs) > 1 ); // compute the total number of IDs nIdMax = 0; Vec_PtrForEachEntry( Aig_Man_t *, vAigs, pAig, i ) nIdMax += Aig_ManObjNumMax(pAig); // partition the first AIG in the array pAig = (Aig_Man_t *)Vec_PtrEntry( vAigs, 0 ); vParts = Aig_ManPartitionSmart( pAig, nPartSize, 0, NULL ); // start the total fraiged AIG pAigTotal = Aig_ManStartFrom( pAig ); Aig_ManReprStart( pAigTotal, nIdMax ); vOutsTotal = Vec_PtrStart( Aig_ManCoNum(pAig) ); // set the PI numbers Vec_PtrForEachEntry( Aig_Man_t *, vAigs, pAig, i ) Aig_ManForEachCi( pAig, pObj, k ) pObj->pNext = (Aig_Obj_t *)(long)k; // Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "unset progressbar" ); // create the total fraiged AIG vPartSupp = Vec_IntAlloc( 100 ); // maps part PI num into total PI num Vec_PtrForEachEntry( Vec_Int_t *, vParts, vPart, i ) { // derive the partition AIG pAigPart = Aig_ManStart( 5000 ); // pAigPart->pName = Extra_UtilStrsav( pAigPart->pName ); Vec_IntClear( vPartSupp ); Vec_PtrForEachEntry( Aig_Man_t *, vAigs, pAig, k ) { vOuts = Aig_ManDupPart( pAigPart, pAig, vPart, vPartSupp, 0 ); if ( k == 0 ) { Vec_PtrForEachEntry( Aig_Obj_t *, vOuts, pObj, m ) Aig_ObjCreateCo( pAigPart, pObj ); } Vec_PtrFree( vOuts ); } // derive the total AIG from the partitioned AIG vOuts = Aig_ManDupPart( pAigTotal, pAigPart, vPart, vPartSupp, 1 ); // add to the outputs Vec_PtrForEachEntry( Aig_Obj_t *, vOuts, pObj, k ) { assert( Vec_PtrEntry( vOutsTotal, Vec_IntEntry(vPart,k) ) == NULL ); Vec_PtrWriteEntry( vOutsTotal, Vec_IntEntry(vPart,k), pObj ); } Vec_PtrFree( vOuts ); // store contents of pData pointers ppData = ABC_ALLOC( void *, Aig_ManObjNumMax(pAigPart) ); Aig_ManForEachObj( pAigPart, pObj, k ) ppData[k] = pObj->pData; // report the process if ( fVerbose ) printf( "Part %4d (out of %4d) PI = %5d. PO = %5d. And = %6d. Lev = %4d.\r", i+1, Vec_PtrSize(vParts), Aig_ManCiNum(pAigPart), Aig_ManCoNum(pAigPart), Aig_ManNodeNum(pAigPart), Aig_ManLevelNum(pAigPart) ); // compute equivalence classes (to be stored in pNew->pReprs) pAig = Fra_FraigChoice( pAigPart, nConfMax, nLevelMax ); Aig_ManStop( pAig ); // reset the pData pointers Aig_ManForEachObj( pAigPart, pObj, k ) pObj->pData = ppData[k]; ABC_FREE( ppData ); // transfer representatives to the total AIG if ( pAigPart->pReprs ) Aig_ManTransferRepr( pAigTotal, pAigPart ); Aig_ManStop( pAigPart ); } if ( fVerbose ) printf( " \r" ); Vec_VecFree( (Vec_Vec_t *)vParts ); Vec_IntFree( vPartSupp ); // Cmd_CommandExecute( Abc_FrameGetGlobalFrame(), "set progressbar" ); // clear the PI numbers Vec_PtrForEachEntry( Aig_Man_t *, vAigs, pAig, i ) Aig_ManForEachCi( pAig, pObj, k ) pObj->pNext = NULL; // add the outputs in the same order Vec_PtrForEachEntry( Aig_Obj_t *, vOutsTotal, pObj, i ) Aig_ObjCreateCo( pAigTotal, pObj ); Vec_PtrFree( vOutsTotal ); // derive the result of choicing pAig = Aig_ManRehash( pAigTotal ); // create the equivalent nodes lists Aig_ManMarkValidChoices( pAig ); // reconstruct the network vPios = Aig_ManOrderPios( pAig, (Aig_Man_t *)Vec_PtrEntry(vAigs,0) ); pAig = Aig_ManDupDfsGuided( pTemp = pAig, vPios ); Aig_ManStop( pTemp ); Vec_PtrFree( vPios ); // duplicate the timing manager pTemp = (Aig_Man_t *)Vec_PtrEntry( vAigs, 0 ); if ( pTemp->pManTime ) pAig->pManTime = Tim_ManDup( (Tim_Man_t *)pTemp->pManTime, 0 ); // reset levels Aig_ManChoiceLevel( pAig ); return pAig; } /**Function************************************************************* Synopsis [Performs partitioned choice computation.] Description [Assumes that each output in the second AIG cannot have more supp vars than the same output in the first AIG.] SideEffects [] SeeAlso [] ***********************************************************************/ Aig_Man_t * Aig_ManFraigPartitioned( Aig_Man_t * pAig, int nPartSize, int nConfMax, int nLevelMax, int fVerbose ) { // extern Aig_Man_t * Fra_FraigChoice( Aig_Man_t * pManAig, int nConfMax, int nLevelMax ); Aig_Man_t * pAigPart, * pAigTemp; Vec_Int_t * vPart; Vec_Ptr_t * vParts; Aig_Obj_t * pObj; void ** ppData; int i, k; // partition the outputs of the AIG vParts = Aig_ManPartitionNaive( pAig, nPartSize ); // start the equivalence classes Aig_ManReprStart( pAig, Aig_ManObjNumMax(pAig) ); // set the PI numbers Aig_ManSetCioIds( pAig ); // create the total fraiged AIG Vec_PtrForEachEntry( Vec_Int_t *, vParts, vPart, i ) { // derive the partition AIG pAigPart = Aig_ManDupPartAll( pAig, vPart ); // store contents of pData pointers ppData = ABC_ALLOC( void *, Aig_ManObjNumMax(pAigPart) ); Aig_ManForEachObj( pAigPart, pObj, k ) ppData[k] = pObj->pData; // report the process if ( fVerbose ) printf( "Part %4d (out of %4d) PI = %5d. PO = %5d. And = %6d. Lev = %4d.\r", i+1, Vec_PtrSize(vParts), Aig_ManCiNum(pAigPart), Aig_ManCoNum(pAigPart), Aig_ManNodeNum(pAigPart), Aig_ManLevelNum(pAigPart) ); // compute equivalence classes (to be stored in pNew->pReprs) pAigTemp = Fra_FraigChoice( pAigPart, nConfMax, nLevelMax ); Aig_ManStop( pAigTemp ); // reset the pData pointers Aig_ManForEachObj( pAigPart, pObj, k ) pObj->pData = ppData[k]; ABC_FREE( ppData ); // transfer representatives to the total AIG if ( pAigPart->pReprs ) Aig_ManTransferRepr( pAig, pAigPart ); Aig_ManStop( pAigPart ); } if ( fVerbose ) printf( " \r" ); Vec_VecFree( (Vec_Vec_t *)vParts ); // clear the PI numbers Aig_ManCleanCioIds( pAig ); // derive the result of choicing return Aig_ManDupRepr( pAig, 0 ); } /**Function************************************************************* Synopsis [Set the representative.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Aig_ObjSetRepr_( Aig_Man_t * p, Aig_Obj_t * pNode1, Aig_Obj_t * pNode2 ) { assert( p->pReprs != NULL ); assert( !Aig_IsComplement(pNode1) ); assert( !Aig_IsComplement(pNode2) ); assert( pNode1->Id < p->nReprsAlloc ); assert( pNode2->Id < p->nReprsAlloc ); if ( pNode1 == pNode2 ) return; if ( pNode1->Id < pNode2->Id ) p->pReprs[pNode2->Id] = pNode1; else p->pReprs[pNode1->Id] = pNode2; } /**Function************************************************************* Synopsis [Constructively accumulates choices.] Description [pNew is a new AIG with choices under construction. pPrev is the AIG preceding pThis in the order of deriving choices. pThis is the current AIG to be added to pNew while creating choices.] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_ManChoiceConstructiveOne( Aig_Man_t * pNew, Aig_Man_t * pPrev, Aig_Man_t * pThis ) { Aig_Obj_t * pObj, * pObjNew; int i; assert( Aig_ManCiNum(pNew) == Aig_ManCiNum(pPrev) ); assert( Aig_ManCiNum(pNew) == Aig_ManCiNum(pThis) ); assert( Aig_ManCoNum(pNew) == Aig_ManCoNum(pPrev) ); assert( Aig_ManCoNum(pNew) == Aig_ManCoNum(pThis) ); // make sure the nodes of pPrev point to pNew Aig_ManForEachObj( pNew, pObj, i ) pObj->fMarkB = 1; Aig_ManForEachObj( pPrev, pObj, i ) assert( Aig_Regular((Aig_Obj_t *)pObj->pData)->fMarkB ); Aig_ManForEachObj( pNew, pObj, i ) pObj->fMarkB = 0; // make sure the nodes of pThis point to pPrev Aig_ManForEachObj( pPrev, pObj, i ) pObj->fMarkB = 1; Aig_ManForEachObj( pPrev, pObj, i ) pObj->fMarkB = 0; // remap nodes of pThis on top of pNew using pPrev pObj = Aig_ManConst1(pThis); pObj->pData = Aig_ManConst1(pNew); Aig_ManForEachCi( pThis, pObj, i ) pObj->pData = Aig_ManCi(pNew, i); Aig_ManForEachCo( pThis, pObj, i ) pObj->pData = Aig_ManCo(pNew, i); // go through the nodes in the topological order Aig_ManForEachNode( pThis, pObj, i ) pObj->pData = Aig_And( pNew, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) ); // set the inputs of POs as equivalent Aig_ManForEachCo( pThis, pObj, i ) { pObjNew = Aig_ObjFanin0( Aig_ManCo(pNew,i) ); // pObjNew and Aig_ObjFanin0(pObj)->pData are equivalent Aig_ObjSetRepr_( pNew, pObjNew, Aig_Regular((Aig_Obj_t *)Aig_ObjFanin0(pObj)->pData) ); } } /**Function************************************************************* Synopsis [Constructively accumulates choices.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Aig_ManChoiceEval( Aig_Man_t * p ) { Vec_Ptr_t * vSupp; Aig_Obj_t * pNode, * pTemp; int i, Counter; vSupp = Vec_PtrAlloc( 100 ); Aig_ManForEachNode( p, pNode, i ) { if ( !Aig_ObjIsChoice(p, pNode) ) continue; Counter = 0; for ( pTemp = pNode; pTemp; pTemp = Aig_ObjEquiv(p, pTemp) ) Counter++; printf( "Choice node = %5d. Level = %2d. Choices = %d. { ", pNode->Id, pNode->Level, Counter ); for ( pTemp = pNode; pTemp; pTemp = Aig_ObjEquiv(p, pTemp) ) { Counter = Aig_NodeMffcSupp( p, pTemp, 0, vSupp ); printf( "S=%d N=%d L=%d ", Vec_PtrSize(vSupp), Counter, pTemp->Level ); } printf( "}\n" ); } Vec_PtrFree( vSupp ); } /**Function************************************************************* Synopsis [Constructively accumulates choices.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Aig_Man_t * Aig_ManChoiceConstructive( Vec_Ptr_t * vAigs, int fVerbose ) { Vec_Ptr_t * vPios; Aig_Man_t * pNew, * pThis, * pPrev, * pTemp; int i; // start AIG with choices pPrev = (Aig_Man_t *)Vec_PtrEntry( vAigs, 0 ); pNew = Aig_ManDupOrdered( pPrev ); // create room for equivalent nodes and representatives assert( pNew->pReprs == NULL ); pNew->nReprsAlloc = Vec_PtrSize(vAigs) * Aig_ManObjNumMax(pNew); pNew->pReprs = ABC_ALLOC( Aig_Obj_t *, pNew->nReprsAlloc ); memset( pNew->pReprs, 0, sizeof(Aig_Obj_t *) * pNew->nReprsAlloc ); // add other AIGs one by one Vec_PtrForEachEntryStart( Aig_Man_t *, vAigs, pThis, i, 1 ) { Aig_ManChoiceConstructiveOne( pNew, pPrev, pThis ); pPrev = pThis; } // derive the result of choicing pNew = Aig_ManRehash( pNew ); // create the equivalent nodes lists Aig_ManMarkValidChoices( pNew ); // reconstruct the network vPios = Aig_ManOrderPios( pNew, (Aig_Man_t *)Vec_PtrEntry( vAigs, 0 ) ); pNew = Aig_ManDupDfsGuided( pTemp = pNew, vPios ); Aig_ManStop( pTemp ); Vec_PtrFree( vPios ); // duplicate the timing manager pTemp = (Aig_Man_t *)Vec_PtrEntry( vAigs, 0 ); if ( pTemp->pManTime ) pNew->pManTime = Tim_ManDup( (Tim_Man_t *)pTemp->pManTime, 0 ); // reset levels Aig_ManChoiceLevel( pNew ); return pNew; } /* Vec_Ptr_t * vPios; vPios = Aig_ManOrderPios( pMan, pAig ); Vec_PtrFree( vPios ); */ //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END