Adding printout of slack distribution for mapped networks.

3 files changed, 328 insertions, 3 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                                ///
 ////////////////////////////////////////////////////////////////////////
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index ad3673d0..7e751ab0 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -29139,7 +29139,7 @@ int Abc_CommandAbc9Ps( Abc_Frame_t * pAbc, int argc, char ** argv )
     int c, fBest = 0;
     memset( pPars, 0, sizeof(Gps_Par_t) );
     Extra_UtilGetoptReset();
-    while ( ( c = Extra_UtilGetopt( argc, argv, "Dtpcnlmasbh" ) ) != EOF )
+    while ( ( c = Extra_UtilGetopt( argc, argv, "Dtpcnlmaszbh" ) ) != EOF )
     {
         switch ( c )
         {
@@ -29165,6 +29165,9 @@ int Abc_CommandAbc9Ps( Abc_Frame_t * pAbc, int argc, char ** argv )
             pPars->fMiter ^= 1;
             break;
         case 's':
+            pPars->fSlacks ^= 1;
+            break;
+        case 'z':
             pPars->fSkipMap ^= 1;
             break;
         case 'D':
@@ -29206,7 +29209,7 @@ int Abc_CommandAbc9Ps( Abc_Frame_t * pAbc, int argc, char ** argv )
     return 0;
 
 usage:
-    Abc_Print( -2, "usage: &ps [-tpcnlmasbh] [-D file]\n" );
+    Abc_Print( -2, "usage: &ps [-tpcnlmaszbh] [-D file]\n" );
     Abc_Print( -2, "\t          prints stats of the current AIG\n" );
     Abc_Print( -2, "\t-t      : toggle printing BMC tents [default = %s]\n",                pPars->fTents? "yes": "no" );
     Abc_Print( -2, "\t-p      : toggle printing switching activity [default = %s]\n",       pPars->fSwitch? "yes": "no" );
@@ -29215,7 +29218,8 @@ usage:
     Abc_Print( -2, "\t-l      : toggle printing LUT size profile [default = %s]\n",         pPars->fLutProf? "yes": "no" );
     Abc_Print( -2, "\t-m      : toggle printing MUX/XOR statistics [default = %s]\n",       pPars->fMuxXor? "yes": "no" );
     Abc_Print( -2, "\t-a      : toggle printing miter statistics [default = %s]\n",         pPars->fMiter? "yes": "no" );
-    Abc_Print( -2, "\t-s      : skip mapping statistics even if mapped [default = %s]\n",   pPars->fSkipMap? "yes": "no" );
+    Abc_Print( -2, "\t-s      : toggle printing slack distribution [default = %s]\n",       pPars->fSlacks? "yes": "no" );
+    Abc_Print( -2, "\t-z      : skip mapping statistics even if mapped [default = %s]\n",   pPars->fSkipMap? "yes": "no" );
     Abc_Print( -2, "\t-b      : toggle printing saved AIG statistics [default = %s]\n",     fBest? "yes": "no" );
     Abc_Print( -2, "\t-D file : file name to dump statistics [default = none]\n" );
     Abc_Print( -2, "\t-h      : print the command usage\n");