Adding print-out of critical path for mapped AIGs to &show.

2 files changed, 302 insertions, 10 deletions

diff --git a/src/aig/gia/gia.h b/src/aig/gia/gia.h
index 7cf1feff..68060119 100644
--- a/src/aig/gia/gia.h
+++ b/src/aig/gia/gia.h
@@ -1426,7 +1426,7 @@ extern Gia_Man_t *         Gia_ManCleanupOutputs( Gia_Man_t * p, int nOutputs );
 extern Gia_Man_t *         Gia_ManSeqCleanup( Gia_Man_t * p );
 extern Gia_Man_t *         Gia_ManSeqStructSweep( Gia_Man_t * p, int fConst, int fEquiv, int fVerbose );
 /*=== giaShow.c ===========================================================*/
-extern void                Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds );
+extern void                Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds, int fPath );
 /*=== giaShrink.c ===========================================================*/
 extern Gia_Man_t *         Gia_ManMapShrink4( Gia_Man_t * p, int fKeepLevel, int fVerbose );
 extern Gia_Man_t *         Gia_ManMapShrink6( Gia_Man_t * p, int nFanoutMax, int fKeepLevel, int fVerbose );
diff --git a/src/aig/gia/giaShow.c b/src/aig/gia/giaShow.c
index 5589d384..28e874bf 100644
--- a/src/aig/gia/giaShow.c
+++ b/src/aig/gia/giaShow.c
@@ -46,6 +46,294 @@ ABC_NAMESPACE_IMPL_START
   SeeAlso     []
 
 ***********************************************************************/
+void Gia_ShowPath( Gia_Man_t * p, char * pFileName )
+{
+    FILE * pFile;
+    Gia_Obj_t * pNode;
+    Vec_Bit_t * vPath = Vec_BitStart( Gia_ManObjNum(p) );
+    int i, k, iFan, LevelMax, nLevels, * pLevels, Level, Prev;
+    int nLuts = 0, nNodes = 0, nEdges = 0, nEdgesAll = 0;
+    assert( Gia_ManHasMapping(p) );
+
+    // set critical CO drivers
+    nLevels = Gia_ManLutLevel( p, &pLevels );
+    Gia_ManForEachCoDriverId( p, iFan, i )
+        if ( pLevels[iFan] == nLevels )
+            Vec_BitWriteEntry( vPath, iFan, 1 );
+
+    // set critical internal nodes
+    Gia_ManForEachLutReverse( p, i )
+    { 
+        nLuts++;
+        if ( !Vec_BitEntry(vPath, i) )
+            continue;
+        nNodes++;
+        Gia_LutForEachFanin( p, i, iFan, k )
+        {
+            if ( pLevels[iFan] +1 < pLevels[i] )
+                continue;
+            assert( pLevels[iFan] + 1 == pLevels[i] );
+            Vec_BitWriteEntry( vPath, iFan, 1 );
+            nEdges++;
+            //printf( "%d -> %d\n", i, iFan );
+        }
+    }
+
+    if ( nNodes > 500 )
+    {
+        ABC_FREE( pLevels );
+        Vec_BitFree( vPath );
+        fprintf( stdout, "Cannot visualize AIG with more than 500 critical nodes.\n" );
+        return;
+    }
+    if ( (pFile = fopen( pFileName, "w" )) == NULL )
+    {
+        ABC_FREE( pLevels );
+        Vec_BitFree( vPath );
+        fprintf( stdout, "Cannot open the intermediate file \"%s\".\n", pFileName );
+        return;
+    }
+
+    Vec_IntFreeP( &p->vLevels );
+    p->vLevels = Vec_IntAllocArray( pLevels, Gia_ManObjNum(p) );
+
+    // compute CO levels
+    LevelMax = 1 + nLevels;
+    Gia_ManForEachCo( p, pNode, i )
+        Vec_IntWriteEntry( p->vLevels, Gia_ObjId(p, pNode), LevelMax );
+
+    // write the DOT header
+    fprintf( pFile, "# %s\n",  "AIG structure generated by GIA package" );
+    fprintf( pFile, "\n" );
+    fprintf( pFile, "digraph AIG {\n" );
+    fprintf( pFile, "size = \"7.5,10\";\n" );
+//  fprintf( pFile, "ranksep = 0.5;\n" );
+//  fprintf( pFile, "nodesep = 0.5;\n" );
+    fprintf( pFile, "center = true;\n" );
+//  fprintf( pFile, "orientation = landscape;\n" );
+//  fprintf( pFile, "edge [fontsize = 10];\n" );
+//  fprintf( pFile, "edge [dir = none];\n" );
+    fprintf( pFile, "edge [dir = back];\n" );
+    fprintf( pFile, "\n" );
+
+    // labels on the left of the picture
+    fprintf( pFile, "{\n" );
+    fprintf( pFile, "  node [shape = plaintext];\n" );
+    fprintf( pFile, "  edge [style = invis];\n" );
+    fprintf( pFile, "  LevelTitle1 [label=\"\"];\n" );
+    fprintf( pFile, "  LevelTitle2 [label=\"\"];\n" );
+    // generate node names with labels
+    for ( Level = LevelMax; Level >= 0; Level-- )
+    {
+        // the visible node name
+        fprintf( pFile, "  Level%d", Level );
+        fprintf( pFile, " [label = " );
+        // label name
+        fprintf( pFile, "\"" );
+        fprintf( pFile, "\"" );
+        fprintf( pFile, "];\n" );
+    }
+
+    // genetate the sequence of visible/invisible nodes to mark levels
+    fprintf( pFile, "  LevelTitle1 ->  LevelTitle2 ->" );
+    for ( Level = LevelMax; Level >= 0; Level-- )
+    {
+        // the visible node name
+        fprintf( pFile, "  Level%d",  Level );
+        // the connector
+        if ( Level != 0 )
+            fprintf( pFile, " ->" );
+        else
+            fprintf( pFile, ";" );
+    }
+    fprintf( pFile, "\n" );
+    fprintf( pFile, "}" );
+    fprintf( pFile, "\n" );
+    fprintf( pFile, "\n" );
+
+    // generate title box on top
+    fprintf( pFile, "{\n" );
+    fprintf( pFile, "  rank = same;\n" );
+    fprintf( pFile, "  LevelTitle1;\n" );
+    fprintf( pFile, "  title1 [shape=plaintext,\n" );
+    fprintf( pFile, "          fontsize=20,\n" );
+    fprintf( pFile, "          fontname = \"Times-Roman\",\n" );
+    fprintf( pFile, "          label=\"" );
+    fprintf( pFile, "%s", "AIG structure visualized by ABC" );
+    fprintf( pFile, "\\n" );
+    fprintf( pFile, "Benchmark \\\"%s\\\". ", "aig" );
+//    fprintf( pFile, "Time was %s. ",  Extra_TimeStamp() );
+    fprintf( pFile, "\"\n" );
+    fprintf( pFile, "         ];\n" );
+    fprintf( pFile, "}" );
+    fprintf( pFile, "\n" );
+    fprintf( pFile, "\n" );
+
+    // generate statistics box
+    fprintf( pFile, "{\n" );
+    fprintf( pFile, "  rank = same;\n" );
+    fprintf( pFile, "  LevelTitle2;\n" );
+    fprintf( pFile, "  title2 [shape=plaintext,\n" );
+    fprintf( pFile, "          fontsize=18,\n" );
+    fprintf( pFile, "          fontname = \"Times-Roman\",\n" );
+    fprintf( pFile, "          label=\"" );
+    fprintf( pFile, "The critical path contains %d LUTs with %d critical edges and spans %d levels.", nNodes, nEdges, nLevels );
+    fprintf( pFile, "\\n" );
+    fprintf( pFile, "\"\n" );
+    fprintf( pFile, "         ];\n" );
+    fprintf( pFile, "}" );
+    fprintf( pFile, "\n" );
+    fprintf( pFile, "\n" );
+
+    // generate the COs
+    fprintf( pFile, "{\n" );
+    fprintf( pFile, "  rank = same;\n" );
+    // the labeling node of this level
+    fprintf( pFile, "  Level%d;\n",  LevelMax );
+    // generate the CO nodes
+    Gia_ManForEachCo( p, pNode, i )
+    {
+        if ( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) < nLevels )
+            continue;
+        assert( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) == nLevels );
+        fprintf( pFile, "  Node%d [label = \"%d\"", Gia_ObjId(p, pNode), Gia_ObjId(p, pNode) ); 
+        fprintf( pFile, ", shape = %s", "invtriangle" );
+        fprintf( pFile, ", color = coral, fillcolor = coral" );
+        fprintf( pFile, "];\n" );
+    }
+    fprintf( pFile, "}" );
+    fprintf( pFile, "\n" );
+    fprintf( pFile, "\n" );
+
+    // generate nodes of each rank
+    for ( Level = LevelMax - 1; Level > 0; Level-- )
+    {
+        fprintf( pFile, "{\n" );
+        fprintf( pFile, "  rank = same;\n" );
+        // the labeling node of this level
+        fprintf( pFile, "  Level%d;\n",  Level );
+        Gia_ManForEachObj( p, pNode, i )
+        {
+            if ( (int)Gia_ObjLevel(p, pNode) != Level || !Vec_BitEntry(vPath, i) )
+                continue;
+            fprintf( pFile, "  Node%d [label = \"%d:%d\"", i, i, Gia_ObjIsAnd(pNode)? Gia_ObjLutSize(p, i) : 0 ); 
+            fprintf( pFile, ", shape = ellipse" );
+            if ( pNode->fMark0 )
+                fprintf( pFile, ", style = filled" );
+            fprintf( pFile, "];\n" );
+        }
+        fprintf( pFile, "}" );
+        fprintf( pFile, "\n" );
+        fprintf( pFile, "\n" );
+    }
+
+    // generate the CI nodes
+    fprintf( pFile, "{\n" );
+    fprintf( pFile, "  rank = same;\n" );
+    // the labeling node of this level
+    fprintf( pFile, "  Level%d;\n",  0 );
+    // generate the CI nodes
+    Gia_ManForEachCi( p, pNode, i )
+    {
+        if ( !Vec_BitEntry(vPath, Gia_ObjId(p, pNode)) )
+            continue;
+        fprintf( pFile, "  Node%d [label = \"%d\"", Gia_ObjId(p, pNode), Gia_ObjId(p, pNode) ); 
+        fprintf( pFile, ", shape = %s", "triangle" );
+        fprintf( pFile, ", color = coral, fillcolor = coral" );
+        fprintf( pFile, "];\n" );
+    }
+    fprintf( pFile, "}" );
+    fprintf( pFile, "\n" );
+    fprintf( pFile, "\n" );
+
+    // generate invisible edges from the square down
+    fprintf( pFile, "title1 -> title2 [style = invis];\n" );
+    Gia_ManForEachCo( p, pNode, i )
+    {
+        if ( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) < nLevels )
+            continue;
+        fprintf( pFile, "title2 -> Node%d [style = invis];\n", Gia_ObjId(p, pNode) );
+    }
+    // generate invisible edges among the COs
+    Prev = -1;
+    Gia_ManForEachCo( p, pNode, i )
+    {
+        if ( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) < nLevels )
+            continue;
+        assert( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) == nLevels );
+        if ( Prev >= 0 )
+            fprintf( pFile, "Node%d -> Node%d [style = invis];\n", Prev, Gia_ObjId(p, pNode) );
+        Prev = Gia_ObjId(p, pNode);
+    }
+    // generate invisible edges among the CIs
+    Prev = -1;
+    Gia_ManForEachCi( p, pNode, i )
+    {
+        if ( !Vec_BitEntry(vPath, Gia_ObjId(p, pNode)) )
+            continue;
+        if ( Prev >= 0 )
+            fprintf( pFile, "Node%d -> Node%d [style = invis];\n", Prev, Gia_ObjId(p, pNode) );
+        Prev = Gia_ObjId(p, pNode);
+    }
+
+    // generate edges
+    Gia_ManForEachObj( p, pNode, i )
+    {
+        if ( Gia_ObjIsCo(pNode) )
+        {
+            if ( Gia_ObjLevel(p, Gia_ObjFanin0(pNode)) == nLevels )
+            {
+                // generate the edge from this node to the next
+                fprintf( pFile, "Node%d",  i );
+                fprintf( pFile, " -> " );
+                fprintf( pFile, "Node%d",  Gia_ObjFaninId0p(p, pNode) );
+                fprintf( pFile, " [" );
+                fprintf( pFile, "style = %s", "bold" );
+                fprintf( pFile, "]" );
+                fprintf( pFile, ";\n" );
+            }
+            continue;
+        }
+        if ( !Gia_ObjIsAnd(pNode) || !Vec_BitEntry(vPath, i) )
+            continue;
+        Gia_LutForEachFanin( p, i, iFan, k )
+        {
+            if ( pLevels[iFan] + 1 < pLevels[i] )
+                continue;
+            assert( pLevels[iFan] + 1 == pLevels[i] );
+            // generate the edge from this node to the next
+            fprintf( pFile, "Node%d",  i );
+            fprintf( pFile, " -> " );
+            fprintf( pFile, "Node%d",  iFan );
+            fprintf( pFile, " [" );
+            fprintf( pFile, "style = %s", "bold" );
+            fprintf( pFile, "]" );
+            fprintf( pFile, ";\n" );
+        }
+    }
+
+    fprintf( pFile, "}" );
+    fprintf( pFile, "\n" );
+    fprintf( pFile, "\n" );
+    fclose( pFile );
+
+    Vec_IntFreeP( &p->vLevels );
+    Vec_BitFree( vPath );
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Writes the graph structure of AIG for DOT.]
+
+  Description [Useful for graph visualization using tools such as GraphViz: 
+  http://www.graphviz.org/]
+  
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 void Gia_WriteDotAigSimple( Gia_Man_t * p, char * pFileName, Vec_Int_t * vBold )
 {
     FILE * pFile;
@@ -79,7 +367,7 @@ void Gia_WriteDotAigSimple( Gia_Man_t * p, char * pFileName, Vec_Int_t * vBold )
         Vec_IntWriteEntry( p->vLevels, Gia_ObjId(p, pNode), LevelMax );
 
     // write the DOT header
-    fprintf( pFile, "# %s\n",  "AIG structure generated by IVY package" );
+    fprintf( pFile, "# %s\n",  "AIG structure generated by GIA package" );
     fprintf( pFile, "\n" );
     fprintf( pFile, "digraph AIG {\n" );
     fprintf( pFile, "size = \"7.5,10\";\n" );
@@ -153,7 +441,7 @@ void Gia_WriteDotAigSimple( Gia_Man_t * p, char * pFileName, Vec_Int_t * vBold )
     fprintf( pFile, "          fontsize=18,\n" );
     fprintf( pFile, "          fontname = \"Times-Roman\",\n" );
     fprintf( pFile, "          label=\"" );
-    fprintf( pFile, "The set contains %d logic nodes and spans %d levels.", Gia_ManAndNum(p), LevelMax );
+    fprintf( pFile, "The AIG contains %d nodes and spans %d levels.", Gia_ManAndNum(p), LevelMax-1 );
     fprintf( pFile, "\\n" );
     fprintf( pFile, "\"\n" );
     fprintf( pFile, "         ];\n" );
@@ -388,6 +676,7 @@ void Gia_WriteDotAig( Gia_Man_t * p, char * pFileName, Vec_Int_t * vAdds, Vec_In
     Gia_Obj_t * pNode;//, * pTemp, * pPrev;
     int LevelMax, Prev, Level, i;
     int fConstIsUsed = 0;
+    int nFadds = Ree_ManCountFadds( vAdds );
 
     if ( Gia_ManAndNum(p) > 1000 )
     {
@@ -406,7 +695,7 @@ void Gia_WriteDotAig( Gia_Man_t * p, char * pFileName, Vec_Int_t * vAdds, Vec_In
         Vec_IntWriteEntry( p->vLevels, Gia_ObjId(p, pNode), LevelMax );
 
     // write the DOT header
-    fprintf( pFile, "# %s\n",  "AIG structure generated by IVY package" );
+    fprintf( pFile, "# %s\n",  "AIG structure generated by GIA package" );
     fprintf( pFile, "\n" );
     fprintf( pFile, "digraph AIG {\n" );
     fprintf( pFile, "size = \"7.5,10\";\n" );
@@ -480,7 +769,8 @@ void Gia_WriteDotAig( Gia_Man_t * p, char * pFileName, Vec_Int_t * vAdds, Vec_In
     fprintf( pFile, "          fontsize=18,\n" );
     fprintf( pFile, "          fontname = \"Times-Roman\",\n" );
     fprintf( pFile, "          label=\"" );
-    fprintf( pFile, "The set contains %d logic nodes and spans %d levels.", Gia_ManAndNum(p), LevelMax );
+    fprintf( pFile, "The AIG contains %d nodes, %d full-adders, and %d half-adders, and spans %d levels.", 
+        Gia_ManAndNum(p), nFadds, Vec_IntSize(vAdds)/6-nFadds, LevelMax-1 );
     fprintf( pFile, "\\n" );
     fprintf( pFile, "\"\n" );
     fprintf( pFile, "         ];\n" );
@@ -813,12 +1103,12 @@ void Gia_ShowProcess( Gia_Man_t * p, char * pFileName, Vec_Int_t * vAdds, Vec_In
     Vec_IntFree( vMapXors );
     Vec_IntFree( vOrder );
 }
-void Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds )
+void Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds, int fPath )
 {
     extern void Abc_ShowFile( char * FileNameDot );
     char FileNameDot[200];
     FILE * pFile;
-    Vec_Int_t * vXors, * vAdds = Ree_ManComputeCuts( pMan, &vXors, 0 );
+    Vec_Int_t * vXors = NULL, * vAdds = fAdders ? Ree_ManComputeCuts( pMan, &vXors, 0 ) : NULL;
     sprintf( FileNameDot, "%s", Extra_FileNameGenericAppend(pMan->pName, ".dot") );
     // check that the file can be opened
     if ( (pFile = fopen( FileNameDot, "w" )) == NULL )
@@ -828,15 +1118,17 @@ void Gia_ManShow( Gia_Man_t * pMan, Vec_Int_t * vBold, int fAdders, int fFadds )
     }
     fclose( pFile );
     // generate the file
-    if ( fAdders )
+    if ( fPath )
+        Gia_ShowPath( pMan, FileNameDot );
+    else if ( fAdders )
         Gia_ShowProcess( pMan, FileNameDot, vAdds, vXors, fFadds );
     else
         Gia_WriteDotAigSimple( pMan, FileNameDot, vBold );
     // visualize the file 
     Abc_ShowFile( FileNameDot );
 
-    Vec_IntFree( vAdds );
-    Vec_IntFree( vXors );
+    Vec_IntFreeP( &vAdds );
+    Vec_IntFreeP( &vXors );
 }