Experiments with retiming.

5 files changed, 125 insertions, 29 deletions

diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 3a3ccac6..5546aec9 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -30073,7 +30073,7 @@ int Abc_CommandAbc9Write( Abc_Frame_t * pAbc, int argc, char ** argv )
     int fWriteNewLine = 0;
     int fVerbose = 0;
     Extra_UtilGetoptReset();
-    while ( ( c = Extra_UtilGetopt( argc, argv, "upmlcvh" ) ) != EOF )
+    while ( ( c = Extra_UtilGetopt( argc, argv, "upmlnvh" ) ) != EOF )
     {
         switch ( c )
         {
@@ -30089,7 +30089,7 @@ int Abc_CommandAbc9Write( Abc_Frame_t * pAbc, int argc, char ** argv )
         case 'l':
             fMiniLut ^= 1;
             break;
-        case 'c':
+        case 'n':
             fWriteNewLine ^= 1;
             break;
         case 'v':
@@ -30131,13 +30131,13 @@ int Abc_CommandAbc9Write( Abc_Frame_t * pAbc, int argc, char ** argv )
     return 0;
 
 usage:
-    Abc_Print( -2, "usage: &w [-upmlcvh] <file>\n" );
+    Abc_Print( -2, "usage: &w [-upmlnvh] <file>\n" );
     Abc_Print( -2, "\t         writes the current AIG into the AIGER file\n" );
     Abc_Print( -2, "\t-u     : toggle writing canonical AIG structure [default = %s]\n", fUnique? "yes" : "no" );
     Abc_Print( -2, "\t-p     : toggle writing Verilog with 'and' and 'not' [default = %s]\n", fVerilog? "yes" : "no" );
     Abc_Print( -2, "\t-m     : toggle writing MiniAIG rather than AIGER [default = %s]\n", fMiniAig? "yes" : "no" );
     Abc_Print( -2, "\t-l     : toggle writing MiniLUT rather than AIGER [default = %s]\n", fMiniLut? "yes" : "no" );
-    Abc_Print( -2, "\t-c     : toggle writing \'\\n\' after \'c\' in the AIGER file [default = %s]\n", fWriteNewLine? "yes": "no" );
+    Abc_Print( -2, "\t-n     : toggle writing \'\\n\' after \'c\' in the AIGER file [default = %s]\n", fWriteNewLine? "yes": "no" );
     Abc_Print( -2, "\t-v     : toggle verbose output [default = %s]\n", fVerbose? "yes": "no" );
     Abc_Print( -2, "\t-h     : print the command usage\n");
     Abc_Print( -2, "\t<file> : the file name\n");
diff --git a/src/base/wlc/wlcNtk.c b/src/base/wlc/wlcNtk.c
index 4ac0c66c..52e2d9a1 100644
--- a/src/base/wlc/wlcNtk.c
+++ b/src/base/wlc/wlcNtk.c
@@ -305,7 +305,7 @@ int Wlc_NtkMemUsage( Wlc_Ntk_t * p )
   SeeAlso     []
 
 ***********************************************************************/
-int Wlc_NtkCreateLevels( Wlc_Ntk_t * p )
+int Wlc_NtkCreateLevels_( Wlc_Ntk_t * p )
 {
     Wlc_Obj_t * pObj; 
     int i, k, iFanin, Level, LevelMax = 0;
@@ -346,6 +346,37 @@ int Wlc_NtkCreateLevelsRev( Wlc_Ntk_t * p )
 
 /**Function*************************************************************
 
+  Synopsis    [Assigns object levels.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Wlc_NtkCreateLevels_rec( Wlc_Ntk_t * p, Wlc_Obj_t * pObj )
+{
+    int k, iFanin, Level = 0;
+    if ( Vec_IntEntry(&p->vLevels, Wlc_ObjId(p, pObj)) > 0 )
+        return;
+    Wlc_ObjForEachFanin( pObj, iFanin, k ) if ( iFanin )
+        Wlc_NtkCreateLevels_rec( p, Wlc_NtkObj(p, iFanin) );
+    Wlc_ObjForEachFanin( pObj, iFanin, k ) if ( iFanin )
+        Level = Abc_MaxInt( Level, Wlc_ObjLevelId(p, iFanin) );
+    Vec_IntWriteEntry( &p->vLevels, Wlc_ObjId(p, pObj), Level + 1 );
+}
+int Wlc_NtkCreateLevels( Wlc_Ntk_t * p )
+{
+    Wlc_Obj_t * pObj;  int i;
+    Vec_IntFill( &p->vLevels, Wlc_NtkObjNumMax(p), 0 );
+    Wlc_NtkForEachCo( p, pObj, i )
+        Wlc_NtkCreateLevels_rec( p, pObj );
+    return Vec_IntFindMax( &p->vLevels );
+}
+
+/**Function*************************************************************
+
   Synopsis    [Collects statistics for each side of the miter.]
 
   Description []
diff --git a/src/base/wlc/wlcShow.c b/src/base/wlc/wlcShow.c
index dcd98ebc..6257fb6e 100644
--- a/src/base/wlc/wlcShow.c
+++ b/src/base/wlc/wlcShow.c
@@ -66,7 +66,11 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold )
             pNode->Mark = 1;
 
     // compute levels
-    LevelMax = 1 + Wlc_NtkCreateLevelsRev( p );
+    LevelMax = 1 + Wlc_NtkCreateLevels( p );
+
+//    Wlc_NtkForEachObj( p, pNode, i )
+//        printf( "Obj=%d Lev=%d\n", i, Wlc_ObjLevel(p, pNode) );
+//    printf( "\n" );
 
     // write the DOT header
     fprintf( pFile, "# %s\n",  "WLC structure generated by ABC" );
@@ -188,7 +192,7 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold )
             if ( pNode->Type == WLC_OBJ_CONST )
             {
                 //char * pName = Wlc_ObjName(p, i);
-                fprintf( pFile, "  Node%d [label = \"%d\'h", i, Wlc_ObjRange(pNode) ); 
+                fprintf( pFile, "  Node%d [label = \"%d:%d\'h", i, i, Wlc_ObjRange(pNode) ); 
                 if ( Wlc_ObjRange(pNode) > 64 )
                 {
                     Abc_TtPrintHexArrayRev( pFile, (word *)Wlc_ObjConstValue(pNode), 16 );
@@ -201,15 +205,15 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold )
             else if ( pNode->Type == WLC_OBJ_BUF || pNode->Type == WLC_OBJ_MUX )
                 fprintf( pFile, "  Node%d [label = \"%d\"", i, Wlc_ObjRange(pNode) ); 
             else if ( pNode->Type >= WLC_OBJ_LOGIC_NOT && pNode->Type <= WLC_OBJ_COMP_MOREEQU )
-                fprintf( pFile, "  Node%d [label = \"%s\"", i, Wlc_ObjTypeName(pNode) ); 
+                fprintf( pFile, "  Node%d [label = \"%d:%s\"", i, i, Wlc_ObjTypeName(pNode) ); 
             else
-                fprintf( pFile, "  Node%d [label = \"%s %d\"", i, Wlc_ObjTypeName(pNode), Wlc_ObjRange(pNode) ); 
+                fprintf( pFile, "  Node%d [label = \"%d:%s %d\"", i, i, Wlc_ObjTypeName(pNode), Wlc_ObjRange(pNode) ); 
 
             if ( pNode->Type == WLC_OBJ_ARI_MULTI )
                 fprintf( pFile, ", shape = doublecircle" );
             else if ( pNode->Type >= WLC_OBJ_COMP_EQU && pNode->Type <= WLC_OBJ_COMP_MOREEQU )
                 fprintf( pFile, ", shape = diamond" );
-            else if ( pNode->Type == WLC_OBJ_BIT_SELECT || pNode->Type == WLC_OBJ_BIT_CONCAT )
+            else if ( pNode->Type == WLC_OBJ_BIT_SELECT || pNode->Type == WLC_OBJ_BIT_CONCAT || pNode->Type == WLC_OBJ_FF )
                 fprintf( pFile, ", shape = box" );
             else if ( pNode->Type == WLC_OBJ_BUF || pNode->Type == WLC_OBJ_BIT_ZEROPAD || pNode->Type == WLC_OBJ_BIT_SIGNEXT )
                 fprintf( pFile, ", shape = triangle" );
@@ -237,7 +241,7 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold )
     {
         if ( vBold && !pNode->Mark )
             continue;
-        fprintf( pFile, "  Node%d [label = \"%s %d\"", Wlc_ObjId(p, pNode), Wlc_ObjName(p, Wlc_ObjId(p, pNode)), Wlc_ObjRange(pNode) ); 
+        fprintf( pFile, "  Node%d [label = \"%d:%s %d\"", Wlc_ObjId(p, pNode), Wlc_ObjId(p, pNode), Wlc_ObjName(p, Wlc_ObjId(p, pNode)), Wlc_ObjRange(pNode) ); 
         fprintf( pFile, ", shape = %s", i < Wlc_NtkPiNum(p) ? "triangle" : "box" );
         fprintf( pFile, ", color = coral, fillcolor = coral" );
         fprintf( pFile, "];\n" );
@@ -298,7 +302,7 @@ void Wlc_NtkDumpDot( Wlc_Ntk_t * p, char * pFileName, Vec_Int_t * vBold )
         if ( vBold && !pNode->Mark )
             continue;
         // generate the edge from this node to the next
-        Wlc_ObjForEachFanin( pNode, iFanin, k )
+        Wlc_ObjForEachFanin( pNode, iFanin, k ) if ( iFanin )
         {
             fprintf( pFile, "Node%d",  i );
             fprintf( pFile, " -> " );
diff --git a/src/base/wln/wlnNdr.c b/src/base/wln/wlnNdr.c
index c87100a2..5daee6a7 100644
--- a/src/base/wln/wlnNdr.c
+++ b/src/base/wln/wlnNdr.c
@@ -268,7 +268,8 @@ Wln_Ntk_t * Wln_NtkFromNdr( void * pData )
     assert( i == Vec_PtrSize(vConstStrings) );
     Vec_PtrFree( vConstStrings );
     //Ndr_NtkPrintObjects( pNtk );
-    //Wln_WriteVer( pNtk, "temp_ndr.v", 0, 0 );
+    Wln_WriteVer( pNtk, "temp_ndr.v" );
+    printf( "Dumped design \"%s\" into file \"temp_ndr.v\".\n", pNtk->pName );
     // derive topological order
     pNtk = Wln_NtkDupDfs( pTemp = pNtk );
     Wln_NtkFree( pTemp );
@@ -313,8 +314,18 @@ void Wln_NtkRetimeTest( char * pFileName )
     Wln_Ntk_t * pNtk = Wln_NtkFromNdr( pData );
     Ndr_Delete( pData );
     if ( !Wln_NtkHasInstId(pNtk) )
+    {
+        int iObj;
         printf( "The design has no delay information.\n" );
-    else
+        Wln_NtkCleanInstId(pNtk);
+        Wln_NtkForEachObj( pNtk, iObj )
+            if ( Wln_ObjIsFf(pNtk, iObj) )
+                Wln_ObjSetInstId( pNtk, iObj, 1 );
+            else if ( !Wln_ObjIsCio(pNtk, iObj) && Wln_ObjFaninNum(pNtk, iObj) > 0 )
+                Wln_ObjSetInstId( pNtk, iObj, 10 );
+        printf( "Assuming user-specified delays for internal nodes.\n" );
+    }
+    //else
     {
         Vec_Int_t * vMoves = Wln_NtkRetime( pNtk );
         Vec_IntPrint( vMoves );
diff --git a/src/base/wln/wlnRetime.c b/src/base/wln/wlnRetime.c
index 459af2d9..711e8db1 100644
--- a/src/base/wln/wlnRetime.c
+++ b/src/base/wln/wlnRetime.c
@@ -64,6 +64,41 @@ static inline int *   Wln_RetFanouts( Wln_Ret_t * p, int i ) { return Vec_IntEnt
 
 /**Function*************************************************************
 
+  Synopsis    [Printing procedure.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Wln_RetPrintObj( Wln_Ret_t * p, int iObj )
+{
+    int k, iFanin, Type = Wln_ObjType(p->pNtk, iObj), * pLink;
+    printf( "Obj %6d : Type = %6s  Fanins = %d : ", iObj, Abc_OperName(Type), Wln_ObjFaninNum(p->pNtk, iObj) );
+    Wln_RetForEachFanin( p, iObj, iFanin, pLink, k )
+    {
+        printf( "%5d ", iFanin );
+        if ( !pLink[0] )
+            continue;
+        printf( "(%d : %d %d) ", pLink[0], 
+            Vec_IntEntry(&p->vEdgeLinks, pLink[0]), 
+            Vec_IntEntry(&p->vEdgeLinks, pLink[0]+1) );
+    }
+    printf( "\n" );
+}
+void Wln_RetPrint( Wln_Ret_t * p )
+{
+    int iObj;
+    printf( "Printing %d objects of network \"%s\":\n", Wln_NtkObjNum(p->pNtk), p->pNtk->pName );
+    Wln_NtkForEachObj( p->pNtk, iObj )
+        Wln_RetPrintObj( p, iObj );
+    printf( "\n" );
+}
+
+/**Function*************************************************************
+
   Synopsis    [Retiming manager.]
 
   Description []
@@ -187,6 +222,7 @@ int Wln_RetPropDelay_rec( Wln_Ret_t * p, int iObj )
     int k, iFanin, * pLink, * pDelay = Vec_IntEntryP( &p->vPathDelays, iObj );
     if ( *pDelay >= 0 )
         return *pDelay;
+    *pDelay = 0;
     Wln_RetForEachFanin( p, iObj, iFanin, pLink, k )
         if ( pLink[0] )
             *pDelay = Abc_MaxInt(*pDelay, 0);
@@ -211,7 +247,7 @@ int Wln_RetPropDelay( Wln_Ret_t * p, Vec_Int_t * vFront )
     }
     Vec_IntClear( &p->vSinks );
     Wln_NtkForEachObj( p->pNtk, iObj )
-        if ( !Wln_ObjIsCo(p->pNtk, iObj) )
+        if ( !Wln_ObjIsCio(p->pNtk, iObj) )
         {
             int Delay = Wln_RetPropDelay_rec(p, iObj);
             if ( DelayMax == Delay )
@@ -222,24 +258,27 @@ int Wln_RetPropDelay( Wln_Ret_t * p, Vec_Int_t * vFront )
                 Vec_IntFill( &p->vSinks, 1, iObj );
             }
         }
+
+//    Vec_IntForEachEntry( &p->vPathDelays, iObj, i )
+//        printf( "Obj = %d.  Delay = %d.\n", i, iObj );
+//    printf( "\n" );
+
+//    printf( "Sinks: " );
+//    Vec_IntPrint( &p->vSinks );
+
     return DelayMax;
 }
 
 void Wln_RetFindSources_rec( Wln_Ret_t * p, int iObj )
 {
-    int k, iFanin, * pLink, FaninDelay, fTerm = 1;
+    int k, iFanin, * pLink, FaninDelay;
     if ( Wln_ObjIsCi(p->pNtk, iObj) || Wln_ObjCheckTravId(p->pNtk, iObj) )
         return;
     FaninDelay = Vec_IntEntry( &p->vPathDelays, iObj ) - Vec_IntEntry( &p->vNodeDelays, iObj );
     Wln_RetForEachFanin( p, iObj, iFanin, pLink, k )
-    {
-        if ( !pLink[0] )
-            continue;
-        fTerm = 0;
-        if ( Vec_IntEntry(&p->vPathDelays, iFanin) == FaninDelay )
+        if ( !pLink[0] && Vec_IntEntry(&p->vPathDelays, iFanin) == FaninDelay )
             Wln_RetFindSources_rec( p, iFanin );
-    }
-    if ( fTerm )
+    if ( FaninDelay == 0 )
         Vec_IntPush( &p->vSources, iObj );
 }
 void Wln_RetFindSources( Wln_Ret_t * p )
@@ -249,6 +288,9 @@ void Wln_RetFindSources( Wln_Ret_t * p )
     Wln_NtkIncrementTravId( p->pNtk );
     Vec_IntForEachEntry( &p->vSinks, iObj, i )
         Wln_RetFindSources_rec( p, iObj );
+
+//    printf( "Sources: " );
+//    Vec_IntPrint( &p->vSources );
 }
 
 /**Function*************************************************************
@@ -342,8 +384,8 @@ int Wln_RetRemoveOneFanin( Wln_Ret_t * p, int iObj )
     Wln_RetForEachFanin( p, iObj, iFanin, pLink, k )
     {
         assert( pLink[0] );
-        pFanins[2*k+1] = Vec_IntEntry( &p->vEdgeLinks, pLink[0] );
         iFlop = Vec_IntEntry( &p->vEdgeLinks, pLink[0] + 1 );
+        pFanins[2*k+1] = Vec_IntEntry( &p->vEdgeLinks, pLink[0] );
         assert( Wln_ObjIsFf( p->pNtk, iFlop ) );
         if ( iFlop1 == -1 )
             iFlop1 = iFlop;
@@ -368,12 +410,14 @@ int Wln_RetRemoveOneFanout( Wln_Ret_t * p, int iObj )
 }
 void Wln_RetInsertOneFanin( Wln_Ret_t * p, int iObj, int iFlop )
 {
-    int k, iFanin, * pLink;
+    int k, iHead, iFanin, * pLink;
     int * pFanins  = Wln_RetFanins( p, iObj );
     assert( Wln_ObjIsFf( p->pNtk, iFlop ) );
     Wln_RetForEachFanin( p, iObj, iFanin, pLink, k )
     {
-        int iHead = pFanins[2*k+1];
+        if ( Wln_ObjIsFf(p->pNtk, iObj) && k > 0 )
+            continue;
+        iHead = pFanins[2*k+1];
         pFanins[2*k+1] = Vec_IntSize(&p->vEdgeLinks);
         Vec_IntPushTwo( &p->vEdgeLinks, iHead, iFlop );
     }
@@ -386,7 +430,6 @@ void Wln_RetInsertOneFanout( Wln_Ret_t * p, int iObj, int iFlop )
     {
         if ( pLink[0] )
             pLink = Wln_RetHeadToTail( p, pLink );
-        pLink = Vec_IntEntryP( &p->vEdgeLinks, pLink[0] );
         assert( pLink[0] == 0 );
         pLink[0] = Vec_IntSize(&p->vEdgeLinks);
         Vec_IntPushTwo( &p->vEdgeLinks, 0, iFlop );
@@ -415,13 +458,15 @@ void Wln_RetAddToMoves( Wln_Ret_t * p, Vec_Int_t * vSet, int Delay, int fForward
     int i, iObj;
     if ( vSet == NULL )
     {
+        printf( "*** Recording initial move (0, %d)\n", Delay );
         Vec_IntPushTwo( &p->vMoves, 0, Delay );
         return;
     }
     Vec_IntForEachEntry( vSet, iObj, i )
     {
         int NameId = Vec_IntEntry( &p->pNtk->vNameIds, iObj );
-        Vec_IntPushTwo( &p->vMoves, fForward ? NameId : -NameId, Delay );
+        printf( "*** Recording new move (%d, %d)\n", fForward ? -NameId : NameId, Delay );
+        Vec_IntPushTwo( &p->vMoves, fForward ? -NameId : NameId, Delay );
     }
 }
 
@@ -443,11 +488,13 @@ Vec_Int_t * Wln_NtkRetime( Wln_Ntk_t * pNtk )
     Vec_Int_t * vSinks   = &p->vSinks;
     Vec_Int_t * vFront   = &p->vFront;
     Vec_Int_t * vMoves   = Vec_IntAlloc(0);
+    //Wln_RetPrint( p );
     p->DelayMax = Wln_RetPropDelay( p, NULL );
     Wln_RetFindSources( p );
     Wln_RetAddToMoves( p, NULL, p->DelayMax, 0 );
     while ( Vec_IntSize(vSources) || Vec_IntSize(vSinks) )
     {
+        int DelayMaxPrev = p->DelayMax;
         int fForward  = Vec_IntSize(vSources) && Wln_RetCheckForward( p, vSources );
         int fBackward = Vec_IntSize(vSinks)   && Wln_RetCheckBackward( p, vSinks );
         if ( !fForward && !fBackward )
@@ -466,9 +513,12 @@ Vec_Int_t * Wln_NtkRetime( Wln_Ntk_t * pNtk )
         if ( (fForward && !fBackward) || (fForward && fBackward && Vec_IntSize(vSources) < Vec_IntSize(vSinks)) )
             Wln_RetRetimeForward( p, vSources ), Vec_IntAppend( vFront, vSources ), fForward = 1, fBackward = 0;
         else
-            Wln_RetRetimeBackward( p, vSinks ),  Vec_IntAppend( vFront, vSources ), fForward = 0, fBackward = 1;
+            Wln_RetRetimeBackward( p, vSinks ),  Vec_IntAppend( vFront, vSinks ), fForward = 0, fBackward = 1;
+        //Wln_RetPrint( p );
         p->DelayMax = Wln_RetPropDelay( p, vFront );
         Wln_RetAddToMoves( p, vFront, p->DelayMax, fForward );
+        if ( p->DelayMax > DelayMaxPrev )
+            break;
         Wln_RetFindSources( p );
         if ( 2*Vec_IntSize(&p->vEdgeLinks) > Vec_IntCap(&p->vEdgeLinks) )
             Vec_IntGrow( &p->vEdgeLinks, 4*Vec_IntSize(&p->vEdgeLinks) );