diff options
Diffstat (limited to 'src/aig/gia/giaCone.c')
-rw-r--r-- | src/aig/gia/giaCone.c | 293 |
1 files changed, 291 insertions, 2 deletions
diff --git a/src/aig/gia/giaCone.c b/src/aig/gia/giaCone.c index da4918ed..56dae32a 100644 --- a/src/aig/gia/giaCone.c +++ b/src/aig/gia/giaCone.c @@ -19,6 +19,7 @@ ***********************************************************************/ #include "gia.h" +#include "misc/extra/extra.h" ABC_NAMESPACE_IMPL_START @@ -271,7 +272,42 @@ int Gia_ManConeMark( Gia_Man_t * p, int iOut, int Limit ) SeeAlso [] ***********************************************************************/ -Gia_Man_t * Gia_ManConeExtract( Gia_Man_t * p, int iOut, int nDelta, int nOutsMin, int nOutsMax ) +int Gia_ManCountFlops( Gia_Man_t * p, Vec_Int_t * vOuts ) +{ + int Limit = ABC_INFINITY; + Vec_Int_t * vRoots; + Gia_Obj_t * pObj; + int i, RetValue, iOut; + // start the outputs + vRoots = Vec_IntAlloc( 100 ); + Vec_IntForEachEntry( vOuts, iOut, i ) + { + pObj = Gia_ManPo( p, iOut ); + Vec_IntPush( vRoots, Gia_ObjId(p, pObj) ); + } + // mark internal nodes + Gia_ManIncrementTravId( p ); + Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) ); + Gia_ManForEachObjVec( vRoots, p, pObj, i ) + if ( Gia_ManConeMark_rec( p, pObj, vRoots, Limit ) ) + break; + RetValue = Vec_IntSize( vRoots ) - Vec_IntSize(vOuts); + Vec_IntFree( vRoots ); + return RetValue; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManFindPoPartition3( Gia_Man_t * p, int iOut, int nDelta, int nOutsMin, int nOutsMax, int fVerbose, Vec_Ptr_t ** pvPosEquivs ) { /* int i, Count = 0; @@ -283,11 +319,264 @@ Gia_Man_t * Gia_ManConeExtract( Gia_Man_t * p, int iOut, int nDelta, int nOutsMi // add other outputs as long as they are nDelta away */ - Opa_ManPerform( p ); +// Opa_ManPerform( p ); return NULL; } + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Gia_ManFindPivots( Gia_Man_t * p, int SelectShift, int fVerbose ) +{ + Vec_Int_t * vPivots, * vWeights; + Vec_Int_t * vCount, * vResult; + int i, j, Count, * pPerm, Limit; +/* + Gia_Obj_t * pObj; + // count MUX controls + vCount = Vec_IntStart( Gia_ManObjNum(p) ); + Gia_ManForEachAnd( p, pObj, i ) + { + Gia_Obj_t * pNodeC, * pNodeT, * pNodeE; + if ( !Gia_ObjIsMuxType(pObj) ) + continue; + pNodeC = Gia_ObjRecognizeMux( pObj, &pNodeT, &pNodeE ); + Vec_IntAddToEntry( vCount, Gia_ObjId(p, Gia_Regular(pNodeC)), 1 ); + } +*/ + // count references + Gia_ManCreateRefs( p ); + vCount = Vec_IntAllocArray( p->pRefs, Gia_ManObjNum(p) ); p->pRefs = NULL; + + // collect nodes + vPivots = Vec_IntAlloc( 100 ); + vWeights = Vec_IntAlloc( 100 ); + Vec_IntForEachEntry( vCount, Count, i ) + { + if ( Count < 2 ) continue; + Vec_IntPush( vPivots, i ); + Vec_IntPush( vWeights, Count ); + } + Vec_IntFree( vCount ); + + if ( fVerbose ) + printf( "Selected %d nodes (out of %d) with more than one fanout.\n", Vec_IntSize(vWeights), Gia_ManPiNum(p) + Gia_ManAndNum(p) ); + + // permute + Gia_ManRandom(1); + Gia_ManRandom(0); + for ( i = 0; i < Vec_IntSize(vWeights); i++ ) + { + j = (Gia_ManRandom(0) >> 1) % Vec_IntSize(vWeights); + ABC_SWAP( int, vPivots->pArray[i], vPivots->pArray[j] ); + ABC_SWAP( int, vWeights->pArray[i], vWeights->pArray[j] ); + } + // sort + pPerm = Abc_QuickSortCost( Vec_IntArray(vWeights), Vec_IntSize(vWeights), 1 ); + // select + Limit = Abc_MinInt( 64, Vec_IntSize(vWeights) ); + vResult = Vec_IntAlloc( Limit ); + for ( i = 0; i < Limit; i++ ) + { + j = (i + SelectShift) % Vec_IntSize(vWeights); + if ( fVerbose ) + printf( "%6d : Pivot = %6d Weight = %6d\n", j, Vec_IntEntry(vPivots, pPerm[j]), Vec_IntEntry(vWeights, pPerm[j]) ); + Vec_IntPush( vResult, Vec_IntEntry(vPivots, pPerm[j]) ); + } + + Vec_IntFree( vPivots ); + Vec_IntFree( vWeights ); + ABC_FREE( pPerm ); + + return vResult; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Wrd_t * Gia_ManDeriveSigns( Gia_Man_t * p, Vec_Int_t * vPivots, int fVerbose ) +{ + Vec_Wrd_t * vSigns; + Gia_Obj_t * pObj, * pObjRi; + int i, fChange = 1, Counter; + + Gia_ManFillValue( p ); + Gia_ManForEachObjVec( vPivots, p, pObj, i ) + pObj->Value = i; + + if ( fVerbose ) + printf( "Signature propagation: " ); + vSigns = Vec_WrdStart( Gia_ManObjNum(p) ); + while ( fChange ) + { + fChange = 0; + Gia_ManForEachObj( p, pObj, i ) + { + if ( ~pObj->Value ) + { + assert( pObj->Value >= 0 && pObj->Value < 64 ); + *Vec_WrdEntryP( vSigns, i ) |= ( 1 << pObj->Value ); + } + if ( Gia_ObjIsAnd(pObj) ) + *Vec_WrdEntryP( vSigns, i ) |= Vec_WrdEntry(vSigns, Gia_ObjFaninId0(pObj, i)) | Vec_WrdEntry(vSigns, Gia_ObjFaninId1(pObj, i)); + else if ( Gia_ObjIsCo(pObj) ) + *Vec_WrdEntryP( vSigns, i ) |= Vec_WrdEntry(vSigns, Gia_ObjFaninId0(pObj, i)); + } + Counter = 0; + Gia_ManForEachRiRo( p, pObjRi, pObj, i ) + { + word Value = Vec_WrdEntry(vSigns, Gia_ObjId(p, pObj)); + *Vec_WrdEntryP( vSigns, Gia_ObjId(p, pObj) ) |= Vec_WrdEntry(vSigns, Gia_ObjId(p, pObjRi)); + if ( Value != Vec_WrdEntry(vSigns, Gia_ObjId(p, pObj)) ) + fChange = 1, Counter++; + } + if ( fVerbose ) + printf( "%d ", Counter ); + } + if ( fVerbose ) + printf( "\n" ); + return vSigns; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Ptr_t * Gia_ManHashOutputs( Gia_Man_t * p, Vec_Wrd_t * vSigns, int fVerbose ) +{ + Gia_Obj_t * pObj; + Vec_Ptr_t * vBins; + Vec_Int_t * vBin; + int i, nBins = Abc_PrimeCudd( Gia_ManPoNum(p) ); + int * pBins = ABC_FALLOC( int, nBins ); + // create hash table of outputs + vBins = Vec_PtrAlloc( 1000 ); + Gia_ManForEachPo( p, pObj, i ) + { + word Sign = Vec_WrdEntry( vSigns, Gia_ObjId(p, pObj) ); + int Offset = (int)(Sign % nBins); + if ( pBins[Offset] == -1 ) + { + pBins[Offset] = Vec_PtrSize( vBins ); + vBin = Vec_IntAlloc( 4 ); + Vec_IntPush( vBin, Offset ); + Vec_PtrPush( vBins, vBin ); + } + vBin = (Vec_Int_t *)Vec_PtrEntry( vBins, pBins[Offset] ); + Vec_IntPush( vBin, i ); + } + ABC_FREE( pBins ); + Vec_VecSort( (Vec_Vec_t *)vBins, 1 ); + + if ( fVerbose ) + printf( "Computed %d partitions:\n", Vec_PtrSize(vBins) ); + Vec_PtrForEachEntry( Vec_Int_t *, vBins, vBin, i ) + { + if ( fVerbose ) + { + int Offset = Vec_IntEntry( vBin, 0 ); + word Sign = Vec_WrdEntry( vSigns, Offset ); + printf( "%6d : Support ", i ); + Extra_PrintBinary( stdout, &Offset, 64 ); + printf( " " ); + } + + // remove the first item + ABC_SWAP( int, vBin->pArray[0], vBin->pArray[Vec_IntSize(vBin)-1] ); + Vec_IntPop( vBin ); + Vec_IntSort( vBin, 0 ); + + if ( fVerbose ) + { + printf( "PO = %7d ", Vec_IntSize(vBin) ); + printf( "FF = %7d", Gia_ManCountFlops(p, vBin) ); + printf( "\n" ); + } + } +// printf( "\n" ); + return vBins; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManFindPoPartition2( Gia_Man_t * p, int iStartNum, int nDelta, int nOutsMin, int nOutsMax, int fSetLargest, int fVerbose, Vec_Ptr_t ** pvPosEquivs ) +{ + return NULL; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Gia_Man_t * Gia_ManFindPoPartition( Gia_Man_t * p, int SelectShift, int fSetLargest, int fVerbose, Vec_Ptr_t ** pvPosEquivs ) +{ + Gia_Man_t * pGia = NULL; + Vec_Int_t * vPivots; + Vec_Wrd_t * vSigns; + Vec_Ptr_t * vParts; + Vec_Int_t * vPart; + vPivots = Gia_ManFindPivots( p, SelectShift, fVerbose ); + vSigns = Gia_ManDeriveSigns( p, vPivots, fVerbose ); + Vec_IntFree( vPivots ); + vParts = Gia_ManHashOutputs( p, vSigns, fVerbose ); + Vec_WrdFree( vSigns ); + if ( fSetLargest ) + { + vPart = Vec_VecEntryInt( (Vec_Vec_t *)vParts, 0 ); + pGia = Gia_ManDupCones( p, Vec_IntArray(vPart), Vec_IntSize(vPart), 1 ); + } + if ( pvPosEquivs ) + { + *pvPosEquivs = vParts; + printf( "Partitioning algorithm divided %d POs into %d groups.\n", Gia_ManPoNum(p), Vec_PtrSize(vParts) ); + } + else + Vec_VecFree( (Vec_Vec_t *)vParts ); + return pGia; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |