diff options
Diffstat (limited to 'src/aig')
| -rw-r--r-- | src/aig/gia/gia.h | 1 | ||||
| -rw-r--r-- | src/aig/gia/giaMan.c | 320 |
2 files changed, 321 insertions, 0 deletions
diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h index 3f42a379..cbb98d1c 100644 --- a/src/aig/gia/gia.h +++ b/src/aig/gia/gia.h @@ -228,6 +228,7 @@ struct Gps_Par_t_ int fMuxXor; int fMiter; int fSkipMap; + int fSlacks; char * pDumpFile; }; diff --git a/src/aig/gia/giaMan.c b/src/aig/gia/giaMan.c index 6ca74491..83254756 100644 --- a/src/aig/gia/giaMan.c +++ b/src/aig/gia/giaMan.c @@ -34,6 +34,8 @@ ABC_NAMESPACE_IMPL_START /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// +extern void Gia_ManDfsSlacksPrint( Gia_Man_t * p ); + //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// @@ -555,6 +557,8 @@ void Gia_ManPrintStats( Gia_Man_t * p, Gps_Par_t * pPars ) */ Gia_ManPrintTents( p ); } + if ( pPars->fSlacks ) + Gia_ManDfsSlacksPrint( p ); } /**Function************************************************************* @@ -793,6 +797,322 @@ void Gia_ManPrintNpnClasses( Gia_Man_t * p ) ABC_FREE( pLutClass ); } + +/**Function************************************************************* + + Synopsis [Collects internal nodes and boxes in the DFS order.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManDfsCollect_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vObjs ) +{ + if ( Gia_ObjIsTravIdCurrent( p, pObj ) ) + return; + Gia_ObjSetTravIdCurrent( p, pObj ); + if ( Gia_ObjIsCi(pObj) ) + { + Tim_Man_t * pManTime = (Tim_Man_t *)p->pManTime; + if ( pManTime ) + { + int i, iFirst, nTerms, iBox; + iBox = Tim_ManBoxForCi( pManTime, Gia_ObjCioId(pObj) ); + if ( iBox >= 0 ) // pObj is a box input + { + // mark box outputs + iFirst = Tim_ManBoxOutputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxOutputNum( pManTime, iBox ); + for ( i = 0; i < nTerms; i++ ) + { + pObj = Gia_ManCi( p, iFirst + i ); + Gia_ObjSetTravIdCurrent( p, pObj ); + } + // traverse box inputs + iFirst = Tim_ManBoxInputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxInputNum( pManTime, iBox ); + for ( i = 0; i < nTerms; i++ ) + { + pObj = Gia_ManCo( p, iFirst + i ); + Gia_ManDfsCollect_rec( p, pObj, vObjs ); + } + // save the box + Vec_IntPush( vObjs, -iBox-1 ); + } + } + return; + } + else if ( Gia_ObjIsCo(pObj) ) + { + Gia_ManDfsCollect_rec( p, Gia_ObjFanin0(pObj), vObjs ); + } + else if ( Gia_ObjIsAnd(pObj) ) + { + int iFan, k, iObj = Gia_ObjId(p, pObj); + if ( Gia_ManHasMapping(p) ) + { + assert( Gia_ObjIsLut(p, iObj) ); + Gia_LutForEachFanin( p, iObj, iFan, k ) + Gia_ManDfsCollect_rec( p, Gia_ManObj(p, iFan), vObjs ); + } + else + { + Gia_ManDfsCollect_rec( p, Gia_ObjFanin0(pObj), vObjs ); + Gia_ManDfsCollect_rec( p, Gia_ObjFanin1(pObj), vObjs ); + } + // save the object + Vec_IntPush( vObjs, iObj ); + } + else if ( !Gia_ObjIsConst0(pObj) ) + assert( 0 ); +} +Vec_Int_t * Gia_ManDfsCollect( Gia_Man_t * p ) +{ + Vec_Int_t * vObjs = Vec_IntAlloc( Gia_ManObjNum(p) ); + Gia_Obj_t * pObj; int i; + Gia_ManIncrementTravId( p ); + Gia_ManForEachCo( p, pObj, i ) + Gia_ManDfsCollect_rec( p, pObj, vObjs ); + Gia_ManForEachCi( p, pObj, i ) + Gia_ManDfsCollect_rec( p, pObj, vObjs ); + return vObjs; +} + +/**Function************************************************************* + + Synopsis [Compute arrival/required times.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Gia_ManDfsArrivals( Gia_Man_t * p, Vec_Int_t * vObjs ) +{ + Tim_Man_t * pManTime = (Tim_Man_t *)p->pManTime; + Vec_Int_t * vTimes = Vec_IntStartFull( Gia_ManObjNum(p) ); + Gia_Obj_t * pObj; int j, Entry, k, iFan; + Vec_IntWriteEntry( vTimes, 0, 0 ); + if ( pManTime ) + { + Tim_ManIncrementTravId( pManTime ); + Gia_ManForEachCi( p, pObj, j ) + if ( j < Tim_ManPiNum(pManTime) ) + { + float arrTime = Tim_ManGetCiArrival( pManTime, j ); + Vec_IntWriteEntry( vTimes, Gia_ObjId(p, pObj), (int)arrTime ); + } + } + else + { + Gia_ManForEachCi( p, pObj, j ) + Vec_IntWriteEntry( vTimes, Gia_ObjId(p, pObj), 0 ); + } + Vec_IntForEachEntry( vObjs, Entry, j ) + { + if ( Entry < 0 ) // box + { + int Time0, iFirst, nTerms, iBox = -Entry-1; + assert( iBox >= 0 ); + // set arrivals for box inputs + iFirst = Tim_ManBoxInputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxInputNum( pManTime, iBox ); + for ( k = 0; k < nTerms; k++ ) + { + pObj = Gia_ManCo( p, iFirst + k ); + Time0 = Vec_IntEntry( vTimes, Gia_ObjFaninId0p(p, pObj) ); + assert( Time0 >= 0 ); + Tim_ManSetCoArrival( pManTime, Gia_ObjCioId(pObj), Time0 ); + } + // derive arrivals for box outputs + iFirst = Tim_ManBoxOutputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxOutputNum( pManTime, iBox ); + for ( k = 0; k < nTerms; k++ ) + { + pObj = Gia_ManCi( p, iFirst + k ); + Time0 = Tim_ManGetCiArrival( pManTime, Gia_ObjCioId(pObj) ); + assert( Time0 >= 0 ); + Vec_IntWriteEntry( vTimes, Gia_ObjId(p, pObj), Time0 ); + } + } + else if ( Entry > 0 ) // node + { + int Time0, Time1, TimeMax = 0; + if ( Gia_ManHasMapping(p) ) + { + assert( Gia_ObjIsLut(p, Entry) ); + Gia_LutForEachFanin( p, Entry, iFan, k ) + { + Time0 = Vec_IntEntry( vTimes, iFan ); + assert( Time0 >= 0 ); + TimeMax = Abc_MaxInt( TimeMax, Time0 ); + } + } + else + { + pObj = Gia_ManObj( p, Entry ); + Time0 = Vec_IntEntry( vTimes, Gia_ObjFaninId0(pObj, Entry) ); + Time1 = Vec_IntEntry( vTimes, Gia_ObjFaninId1(pObj, Entry) ); + assert( Time0 >= 0 && Time1 >= 0 ); + TimeMax = Abc_MaxInt( Time0, Time1 ); + } + Vec_IntWriteEntry( vTimes, Entry, TimeMax + 10 ); + } + else assert( 0 ); + } + return vTimes; +} +static inline void Gia_ManDfsUpdateRequired( Vec_Int_t * vTimes, int iObj, int Req ) +{ + int *pTime = Vec_IntEntryP( vTimes, iObj ); + if (*pTime == -1 || *pTime > Req) + *pTime = Req; +} +Vec_Int_t * Gia_ManDfsRequireds( Gia_Man_t * p, Vec_Int_t * vObjs, int ReqTime ) +{ + Tim_Man_t * pManTime = (Tim_Man_t *)p->pManTime; + Vec_Int_t * vTimes = Vec_IntStartFull( Gia_ManObjNum(p) ); + Gia_Obj_t * pObj; + int j, Entry, k, iFan, Req; + Vec_IntWriteEntry( vTimes, 0, 0 ); + if ( pManTime ) + { + int nCoLimit = Gia_ManCoNum(p) - Tim_ManPoNum(pManTime); + Tim_ManIncrementTravId( pManTime ); + //Tim_ManInitPoRequiredAll( pManTime, (float)ReqTime ); + Gia_ManForEachCo( p, pObj, j ) + if ( j >= nCoLimit ) + { + Tim_ManSetCoRequired( pManTime, j, ReqTime ); + Gia_ManDfsUpdateRequired( vTimes, Gia_ObjFaninId0p(p, pObj), ReqTime ); + } + } + else + { + Gia_ManForEachCo( p, pObj, j ) + Gia_ManDfsUpdateRequired( vTimes, Gia_ObjFaninId0p(p, pObj), ReqTime ); + } + Vec_IntForEachEntryReverse( vObjs, Entry, j ) + { + if ( Entry < 0 ) // box + { + int iFirst, nTerms, iBox = -Entry-1; + assert( iBox >= 0 ); + // set requireds for box outputs + iFirst = Tim_ManBoxOutputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxOutputNum( pManTime, iBox ); + for ( k = 0; k < nTerms; k++ ) + { + pObj = Gia_ManCi( p, iFirst + k ); + Req = Vec_IntEntry( vTimes, Gia_ObjId(p, pObj) ); + Req = Req == -1 ? ReqTime : Req; // dangling box output + assert( Req >= 0 ); + Tim_ManSetCiRequired( pManTime, Gia_ObjCioId(pObj), Req ); + } + // derive requireds for box inputs + iFirst = Tim_ManBoxInputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxInputNum( pManTime, iBox ); + for ( k = 0; k < nTerms; k++ ) + { + pObj = Gia_ManCo( p, iFirst + k ); + Req = Tim_ManGetCoRequired( pManTime, Gia_ObjCioId(pObj) ); + assert( Req >= 0 ); + Gia_ManDfsUpdateRequired( vTimes, Gia_ObjFaninId0p(p, pObj), Req ); + } + } + else if ( Entry > 0 ) // node + { + Req = Vec_IntEntry(vTimes, Entry) - 10; + assert( Req >= 0 ); + if ( Gia_ManHasMapping(p) ) + { + assert( Gia_ObjIsLut(p, Entry) ); + Gia_LutForEachFanin( p, Entry, iFan, k ) + Gia_ManDfsUpdateRequired( vTimes, iFan, Req ); + } + else + { + pObj = Gia_ManObj( p, Entry ); + Gia_ManDfsUpdateRequired( vTimes, Gia_ObjFaninId0(pObj, Entry), Req ); + Gia_ManDfsUpdateRequired( vTimes, Gia_ObjFaninId1(pObj, Entry), Req ); + } + } + else assert( 0 ); + } + return vTimes; +} +Vec_Int_t * Gia_ManDfsSlacks( Gia_Man_t * p ) +{ + Vec_Int_t * vSlack = Vec_IntStartFull( Gia_ManObjNum(p) ); + Vec_Int_t * vObjs = Gia_ManDfsCollect( p ); + if ( Vec_IntSize(vObjs) > 0 ) + { + Vec_Int_t * vArrs = Gia_ManDfsArrivals( p, vObjs ); + int Required = Vec_IntFindMax( vArrs ); + Vec_Int_t * vReqs = Gia_ManDfsRequireds( p, vObjs, Required ); + int i, Arr, Req, Arrivals = ABC_INFINITY; + Vec_IntForEachEntry( vReqs, Req, i ) + if ( Req != -1 ) + Arrivals = Abc_MinInt( Arrivals, Req ); + //if ( Arrivals != 0 ) + // printf( "\nGlobal timing check has failed.\n\n" ); + //assert( Arrivals == 0 ); + Vec_IntForEachEntryTwo( vArrs, vReqs, Arr, Req, i ) + { + if ( !Gia_ObjIsAnd(Gia_ManObj(p, i)) ) + continue; + if ( Gia_ManHasMapping(p) && !Gia_ObjIsLut(p, i) ) + continue; + assert( Arr <= Req ); + Vec_IntWriteEntry( vSlack, i, Req - Arr ); + } + Vec_IntFree( vArrs ); + Vec_IntFree( vReqs ); + } + Vec_IntFree( vObjs ); + return vSlack; +} +void Gia_ManDfsSlacksPrint( Gia_Man_t * p ) +{ + Vec_Int_t * vCounts, * vSlacks = Gia_ManDfsSlacks( p ); + int i, Entry, nRange, nTotal; + if ( Vec_IntSize(vSlacks) == 0 ) + { + printf( "Network contains no internal objects.\n" ); + Vec_IntFree( vSlacks ); + return; + } + // compute slacks + Vec_IntForEachEntry( vSlacks, Entry, i ) + if ( Entry != -1 ) + Vec_IntWriteEntry( vSlacks, i, Entry/10 ); + nRange = Vec_IntFindMax( vSlacks ); + // count items + vCounts = Vec_IntStart( nRange + 1 ); + Vec_IntForEachEntry( vSlacks, Entry, i ) + if ( Entry != -1 ) + Vec_IntAddToEntry( vCounts, Entry, 1 ); + // print slack ranges + nTotal = Vec_IntSum( vCounts ); + assert( nTotal > 0 ); + Vec_IntForEachEntry( vCounts, Entry, i ) + { + printf( "Slack range %3d = ", i ); + printf( "[%4d, %4d) ", 10*i, 10*(i+1) ); + printf( "Nodes = %5d ", Entry ); + printf( "(%6.2f %%) ", 100.0*Entry/nTotal ); + printf( "\n" ); + } + Vec_IntFree( vSlacks ); + Vec_IntFree( vCounts ); +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |