diff options
Diffstat (limited to 'src/aig/gia')
-rw-r--r-- | src/aig/gia/gia.h | 6 | ||||
-rw-r--r-- | src/aig/gia/giaEdge.c | 351 | ||||
-rw-r--r-- | src/aig/gia/giaMan.c | 2 | ||||
-rw-r--r-- | src/aig/gia/giaTim.c | 2 |
4 files changed, 360 insertions, 1 deletions
diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 8d3bb198..af29a72e 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -132,6 +132,7 @@ struct Gia_Man_t_ Vec_Int_t * vFanout; // static fanout Vec_Int_t * vMapping; // mapping for each node Vec_Wec_t * vMapping2; // mapping for each node + Vec_Wec_t * vFanouts2; // mapping fanouts Vec_Int_t * vCellMapping; // mapping for each node void * pSatlutWinman; // windowing for SAT-based mapping Vec_Int_t * vPacking; // packing information @@ -139,6 +140,7 @@ struct Gia_Man_t_ char * pCellStr; // cell description Vec_Int_t * vLutConfigs; // LUT configurations Vec_Int_t * vEdgeDelay; // special edge information + Vec_Int_t * vEdgeDelayR; // special edge information Vec_Int_t * vEdge1; // special edge information Vec_Int_t * vEdge2; // special edge information Abc_Cex_t * pCexComb; // combinational counter-example @@ -997,6 +999,8 @@ static inline int Gia_ObjIsLut2( Gia_Man_t * p, int Id ) { re static inline int Gia_ObjLutSize2( Gia_Man_t * p, int Id ) { return Vec_IntSize(Vec_WecEntry(p->vMapping2, Id)); } static inline Vec_Int_t * Gia_ObjLutFanins2( Gia_Man_t * p, int Id ) { return Vec_WecEntry(p->vMapping2, Id); } static inline int Gia_ObjLutFanin2( Gia_Man_t * p, int Id, int i ) { return Vec_IntEntry(Vec_WecEntry(p->vMapping2, Id), i); } +static inline int Gia_ObjLutFanoutNum2( Gia_Man_t * p, int Id ) { return Vec_IntSize(Vec_WecEntry(p->vFanouts2, Id)); } +static inline int Gia_ObjLutFanout2( Gia_Man_t * p, int Id, int i ) { return Vec_IntEntry(Vec_WecEntry(p->vFanouts2, Id), i); } static inline int Gia_ManHasCellMapping( Gia_Man_t * p ) { return p->vCellMapping != NULL; } static inline int Gia_ObjIsCell( Gia_Man_t * p, int iLit ) { return Vec_IntEntry(p->vCellMapping, iLit) != 0; } @@ -1026,6 +1030,8 @@ static inline int Gia_ObjCellId( Gia_Man_t * p, int iLit ) { re for ( i = Vec_IntSize(vIds)-1; i >= 0 && (vVec = Vec_WecEntry(p->vMapping2, (iObj = Vec_IntEntry(vIds, i)))); i-- ) #define Gia_LutForEachFanin2( p, i, iFan, k ) \ for ( k = 0; k < Gia_ObjLutSize2(p,i) && ((iFan = Gia_ObjLutFanin2(p,i,k)),1); k++ ) +#define Gia_LutForEachFanout2( p, i, iFan, k ) \ + for ( k = 0; k < Gia_ObjLutFanoutNum2(p,i) && ((iFan = Gia_ObjLutFanout2(p,i,k)),1); k++ ) #define Gia_ManForEachCell( p, i ) \ for ( i = 2; i < 2*Gia_ManObjNum(p); i++ ) if ( !Gia_ObjIsCell(p, i) ) {} else diff --git a/src/aig/gia/giaEdge.c b/src/aig/gia/giaEdge.c index df738509..b74bbe5c 100644 --- a/src/aig/gia/giaEdge.c +++ b/src/aig/gia/giaEdge.c @@ -633,6 +633,357 @@ int Gia_ManEvalWindow( Gia_Man_t * p, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, V return DelayMax; } + + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Edg_ManToMapping( Gia_Man_t * p ) +{ + int iObj, iFanin, k; + assert( Gia_ManHasMapping(p) ); + Vec_WecFreeP( &p->vMapping2 ); + Vec_WecFreeP( &p->vFanouts2 ); + p->vMapping2 = Vec_WecStart( Gia_ManObjNum(p) ); + p->vFanouts2 = Vec_WecStart( Gia_ManObjNum(p) ); + Gia_ManForEachLut( p, iObj ) + { + assert( Gia_ObjLutSize(p, iObj) <= 4 ); + Gia_LutForEachFanin( p, iObj, iFanin, k ) + { + Vec_WecPush( p->vMapping2, iObj, iFanin ); + Vec_WecPush( p->vFanouts2, iFanin, iObj ); + } + } +} + +/**Function************************************************************* + + Synopsis [Computes delay for the given edge assignment.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Edg_ObjEvalEdgeDelay( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay ) +{ + int DelayEdge = 0; // 2; + int DelayNoEdge = 1; + int i, iFan, Delay, DelayMax = 0; + assert( Gia_ObjIsLut2(p, iObj) ); + Gia_LutForEachFanin2( p, iObj, iFan, i ) + { + Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? DelayEdge : DelayNoEdge); + DelayMax = Abc_MaxInt( DelayMax, Delay ); + } + //printf( "Obj %d - Level %d\n", iObj, DelayMax ); + return DelayMax; +} +int Edg_ManEvalEdgeDelay( Gia_Man_t * p ) +{ + int iLut, Delay, DelayMax = 0; + assert( p->vEdge1 && p->vEdge2 ); + if ( p->vEdgeDelay == NULL ) + p->vEdgeDelay = Vec_IntStart( Gia_ManObjNum(p) ); + else + Vec_IntFill( p->vEdgeDelay, Gia_ManObjNum(p), 0 ); + Gia_ManForEachLut2( p, iLut ) + { + Delay = Edg_ObjEvalEdgeDelay(p, iLut, p->vEdgeDelay); + Vec_IntWriteEntry( p->vEdgeDelay, iLut, Delay ); + DelayMax = Abc_MaxInt( DelayMax, Delay ); + } + return DelayMax; +} + +static inline int Edg_ObjEvalEdgeDelayR( Gia_Man_t * p, int iObj, Vec_Int_t * vDelay ) +{ + int DelayEdge = 0; // 2; + int DelayNoEdge = 1; + int i, iFan, Delay, DelayMax = 0; + assert( Gia_ObjIsLut2(p, iObj) ); + Gia_LutForEachFanout2( p, iObj, iFan, i ) + { + Delay = Vec_IntEntry(vDelay, iFan) + (Gia_ObjHaveEdge(p, iObj, iFan) ? DelayEdge : DelayNoEdge); + DelayMax = Abc_MaxInt( DelayMax, Delay ); + } + //printf( "Obj %d - LevelR %d\n", iObj, DelayMax ); + return DelayMax; +} +int Edg_ManEvalEdgeDelayR( Gia_Man_t * p ) +{ +// int k, DelayNoEdge = 1; + int iLut, Delay, DelayMax = 0; + assert( p->vEdge1 && p->vEdge2 ); + if ( p->vEdgeDelayR == NULL ) + p->vEdgeDelayR = Vec_IntStart( Gia_ManObjNum(p) ); + else + Vec_IntFill( p->vEdgeDelayR, Gia_ManObjNum(p), 0 ); +// Gia_ManForEachCoDriverId( p, iLut, k ) +// Vec_IntWriteEntry( p->vEdgeDelayR, iLut, DelayNoEdge ); + Gia_ManForEachLut2Reverse( p, iLut ) + { + Delay = Edg_ObjEvalEdgeDelayR(p, iLut, p->vEdgeDelayR); + Vec_IntWriteEntry( p->vEdgeDelayR, iLut, Delay ); + DelayMax = Abc_MaxInt( DelayMax, Delay ); + } + return DelayMax; +} + +void Edg_ManCollectCritEdges( Gia_Man_t * p, Vec_Wec_t * vEdges, int DelayMax ) +{ + Vec_Int_t * vLevel; + int k, iLut, Delay1, Delay2; + assert( p->vEdge1 && p->vEdge2 ); + Vec_WecClear( vEdges ); + Vec_WecInit( vEdges, DelayMax + 1 ); + Gia_ManForEachLut2( p, iLut ) + { + Delay1 = Vec_IntEntry( p->vEdgeDelay, iLut ); + Delay2 = Vec_IntEntry( p->vEdgeDelayR, iLut ); + assert( Delay1 + Delay2 <= DelayMax ); + if ( Delay1 + Delay2 == DelayMax ) + Vec_WecPush( vEdges, Delay1, iLut ); + } + // every level should have critical nodes, except the first one + //Vec_WecPrint( vEdges, 0 ); + Vec_WecForEachLevelStart( vEdges, vLevel, k, 1 ) + assert( Vec_IntSize(vLevel) > 0 ); +} + + +/**Function************************************************************* + + Synopsis [Update one node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Edg_ObjImprove( Gia_Man_t * p, int iObj, int nEdgeLimit, int DelayMax, int fVerbose ) +{ + int nFaninsC = 0, nFanoutsC = 0; // critical + int nFaninsEC = 0, nFanoutsEC = 0; // edge-critical + int nFaninsENC = 0, nFanoutsENC = 0; // edge-non-critial + int pFanins[4], pFanouts[4]; + int nEdgeDiff, nEdges = 0, Count = 0; + int i, iNext, Delay1, Delay2; + // count how many fanins have critical edge + Delay1 = Vec_IntEntry( p->vEdgeDelayR, iObj ); + //if ( Delay1 > 1 ) + Gia_LutForEachFanin2( p, iObj, iNext, i ) + { + if ( !Gia_ObjIsAnd(Gia_ManObj(p, iNext)) ) + continue; + Delay2 = Vec_IntEntry( p->vEdgeDelay, iNext ); + if ( Gia_ObjHaveEdge(p, iObj, iNext) ) + { + nEdges++; + assert( Delay1 + Delay2 <= DelayMax ); + if ( Delay1 + Delay2 == DelayMax ) + nFaninsEC++; + else + nFaninsENC++; + } + else + { + assert( Delay1 + Delay2 + 1 <= DelayMax ); + if ( Delay1 + Delay2 + 1 == DelayMax ) + pFanins[nFaninsC++] = iNext; + } + } + // count how many fanouts have critical edge + Delay1 = Vec_IntEntry( p->vEdgeDelay, iObj ); + //if ( Delay2 < DelayMax - 1 ) + Gia_LutForEachFanout2( p, iObj, iNext, i ) + { + //if ( !Gia_ObjIsAnd(Gia_ManObj(p, iNext)) ) + // continue; + assert( Gia_ObjIsAnd(Gia_ManObj(p, iNext)) ); + Delay2 = Vec_IntEntry( p->vEdgeDelayR, iNext ); + if ( Gia_ObjHaveEdge(p, iObj, iNext) ) + { + nEdges++; + assert( Delay1 + Delay2 <= DelayMax ); + if ( Delay1 + Delay2 == DelayMax ) + nFanoutsEC++; + else + nFanoutsENC++; + } + else + { + assert( Delay1 + Delay2 + 1 <= DelayMax ); + if ( Delay1 + Delay2 + 1 == DelayMax ) + { + if ( nFanoutsC < nEdgeLimit ) + pFanouts[nFanoutsC] = iNext; + nFanoutsC++; + } + } + } + if ( fVerbose ) + { + printf( "%8d : ", iObj ); + printf( "Edges = %d ", nEdges ); + printf( "Fanins (all %d EC %d ENC %d C %d) ", + Gia_ObjLutSize2(p, iObj), nFaninsEC, nFaninsENC, nFaninsC ); + printf( "Fanouts (all %d EC %d ENC %d C %d) ", + Gia_ObjLutFanoutNum2(p, iObj), nFanoutsEC, nFanoutsENC, nFanoutsC ); + } + // consider simple cases + assert( nEdges <= nEdgeLimit ); + if ( nEdges == nEdgeLimit ) + { + if ( fVerbose ) + printf( "Full\n" ); + return 0; + } + nEdgeDiff = nEdgeLimit - nEdges; + // check if fanins or fanouts could be improved + if ( nFaninsEC == 0 && nFaninsC && nFaninsC <= nEdgeDiff ) + { + for ( i = 0; i < nFaninsC; i++ ) + if ( Gia_ObjEdgeCount(pFanins[i], p->vEdge1, p->vEdge2) == nEdgeLimit ) + break; + if ( i == nFaninsC ) + { + for ( i = 0; i < nFaninsC; i++ ) + { + Count += Gia_ObjEdgeAdd( iObj, pFanins[i], p->vEdge1, p->vEdge2 ); + Count += Gia_ObjEdgeAdd( pFanins[i], iObj, p->vEdge1, p->vEdge2 ); + } + if ( Count ) + printf( "Wrong number of edges.\n" ); + if ( fVerbose ) + printf( "Fixed %d critical fanins\n", nFaninsC ); + return 1; + } + } + if ( nFanoutsEC == 0 && nFanoutsC && nFanoutsC <= nEdgeDiff ) + { + for ( i = 0; i < nFanoutsC; i++ ) + if ( Gia_ObjEdgeCount(pFanouts[i], p->vEdge1, p->vEdge2) == nEdgeLimit ) + break; + if ( i == nFanoutsC ) + { + for ( i = 0; i < nFanoutsC; i++ ) + { + Count += Gia_ObjEdgeAdd( iObj, pFanouts[i], p->vEdge1, p->vEdge2 ); + Count += Gia_ObjEdgeAdd( pFanouts[i], iObj, p->vEdge1, p->vEdge2 ); + } + if ( Count ) + printf( "Wrong number of edges.\n" ); + if ( fVerbose ) + printf( "Fixed %d critical fanouts\n", nFanoutsC ); + return 1; + } + } + if ( fVerbose ) + printf( "Cannot fix\n" ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Finds edge assignment.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Edg_ManAssignEdgeNew( Gia_Man_t * p, int nEdges, int fVerbose ) +{ + int DelayNoEdge = 1; + int fLevelVerbose = 0; + Vec_Int_t * vLevel; + Vec_Wec_t * vEdges = Vec_WecStart(0); + Vec_Int_t * vEdge1 = NULL, * vEdge2 = NULL; + int DelayD = 0, DelayR = 0, DelayPrev = ABC_INFINITY; + int k, j, i, iLast = -1, iObj; + if ( fVerbose ) + printf( "Running edge assignment with E = %d.\n", nEdges ); + // create fanouts + Edg_ManToMapping( p ); + // create empty assignment + Vec_IntFreeP( &p->vEdge1 ); + Vec_IntFreeP( &p->vEdge2 ); + p->vEdge1 = Vec_IntStart( Gia_ManObjNum(p) ); + p->vEdge2 = Vec_IntStart( Gia_ManObjNum(p) ); + // perform optimization + for ( i = 0; i < 10000; i++ ) + { + // if there is no improvement after 10 iterations, quit + if ( i > iLast + 50 ) + break; + // create delay information + DelayD = Edg_ManEvalEdgeDelay( p ); + DelayR = Edg_ManEvalEdgeDelayR( p ); + assert( DelayD == DelayR + DelayNoEdge ); + if ( DelayPrev > DelayD ) + { + //printf( "Saving backup point at %d levels.\n", DelayD ); + Vec_IntFreeP( &vEdge1 ); vEdge1 = Vec_IntDup( p->vEdge1 ); + Vec_IntFreeP( &vEdge2 ); vEdge2 = Vec_IntDup( p->vEdge2 ); + DelayPrev = DelayD; + iLast = i; + } + if ( fVerbose ) + printf( "\nIter %4d : Delay = %4d\n", i, DelayD ); + // collect critical nodes (nodes with critical edges) + Edg_ManCollectCritEdges( p, vEdges, DelayD ); + // sort levels according to the number of critical edges + if ( fLevelVerbose ) + { + Vec_WecForEachLevel( vEdges, vLevel, k ) + Vec_IntPush( vLevel, k ); + } + Vec_WecSort( vEdges, 0 ); + if ( fLevelVerbose ) + { + Vec_WecForEachLevel( vEdges, vLevel, k ) + { + int Level = Vec_IntPop( vLevel ); + printf( "%d: Level %2d : ", k, Level ); + Vec_IntPrint( vLevel ); + } + } + Vec_WecForEachLevel( vEdges, vLevel, k ) + { + Vec_IntForEachEntry( vLevel, iObj, j ) + if ( Edg_ObjImprove(p, iObj, nEdges, DelayD, fVerbose) ) // improved + break; + if ( j < Vec_IntSize(vLevel) ) + break; + } + if ( k == Vec_WecSize(vEdges) ) // if we could not improve anything, quit + break; + } + Vec_WecFree( vEdges ); + // update to the saved version + Vec_IntFreeP( &p->vEdge1 ); p->vEdge1 = vEdge1; + Vec_IntFreeP( &p->vEdge2 ); p->vEdge2 = vEdge2; + return DelayD; +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// diff --git a/src/aig/gia/giaMan.c b/src/aig/gia/giaMan.c index b7434bff..27dff3ad 100644 --- a/src/aig/gia/giaMan.c +++ b/src/aig/gia/giaMan.c @@ -95,6 +95,7 @@ void Gia_ManStop( Gia_Man_t * p ) Vec_IntFreeP( &p->vCofVars ); Vec_IntFreeP( &p->vLutConfigs ); Vec_IntFreeP( &p->vEdgeDelay ); + Vec_IntFreeP( &p->vEdgeDelayR ); Vec_IntFreeP( &p->vEdge1 ); Vec_IntFreeP( &p->vEdge2 ); Vec_IntFreeP( &p->vUserPiIds ); @@ -117,6 +118,7 @@ void Gia_ManStop( Gia_Man_t * p ) Vec_PtrFreeP( &p->vTtInputs ); Vec_IntFreeP( &p->vMapping ); Vec_WecFreeP( &p->vMapping2 ); + Vec_WecFreeP( &p->vFanouts2 ); Vec_IntFreeP( &p->vCellMapping ); Vec_IntFreeP( &p->vPacking ); Vec_IntFreeP( &p->vConfigs ); diff --git a/src/aig/gia/giaTim.c b/src/aig/gia/giaTim.c index 3d047dee..a3adc9ce 100644 --- a/src/aig/gia/giaTim.c +++ b/src/aig/gia/giaTim.c @@ -364,7 +364,7 @@ Vec_Int_t * Gia_ManOrderWithBoxes( Gia_Man_t * p ) // verify counts assert( curCi == Gia_ManCiNum(p) ); assert( curCo == Gia_ManCoNum(p) ); - assert( Vec_IntSize(vNodes) == Gia_ManObjNum(p) ); + //assert( Vec_IntSize(vNodes) == Gia_ManObjNum(p) ); return vNodes; } |